题解 - Vijos

1

Lifi LV 10 @ 2019-07-29 20:19:55

没用KMP，朴素匹配过的，有点慢。看有些大神没有KMP也0MS，怎么操作？

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#define ULL unsigned long long

using namespace std;

vector<char> vc;

int main()
{
    ULL ans=0;
    char c;
    string a;
    cin>>a;
    int i,j,l=a.length();
    while(scanf("%c",&c)!=EOF)
    {
        vc.push_back(c);
        if(c==a[l-1])
        {
            j=vc.size();
            for(i=1;i<=l;i++)
            {
                if(a[l-i]!=vc[j-i])
                {
                    break;
                }
            }
            if(i==l+1)
            {
                j=l;
                while(j>0)
                {
                    j--;
                    vc.pop_back();
                }
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

0

dkfleet LV 10 @ 2015-03-06 21:41:21

KMP水过.....
读入字符串a和s,对a构造KMP的自动机,然后拿s来匹配,每次匹配把它在自动机上走到的地方记录下来.
当a完全匹配后通过向前的指针把a字符串从s中删除,当前匹配位置设置为删除段的前一个节点.

使用这个方法千万注意,KMP一定要预处理出每个状态对每个字符的转移,而不能直接输入一个字符就按照fail指针往前跳.因为我们从s中删除一个a以后要改变当前匹配状态,这是不能保证平摊复杂度的.

USACO 2015 Feb Gold T1是这道题的多模式串版本..... 就因为上边所述没有注意到被坑掉一个点....

###Code~

#include <cstdio>
#include <fstream>
#include <iostream>

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>

typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
typedef double db;

using namespace std;

inline int getint()
{
int res=0;
char c=getchar();
bool mi=false;
while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
return mi ? -res : res;
}

char a[10000];
char s[2000000];
int f[10000];
int tran[10000][55];
int _pre[2000000];
int*pre=_pre+1;
int _state[2000000];
int*state=_state+1;

int ch(char c)
{ if('a'<=c && c<='z') return c-'a'; else return c-'A'+26; }
char revh(int k)
{ if(k<26) return k+'a'; else return k-26+'A'; }

int n,m;

int main()
{
scanf("%s%s",a,s);
n=strlen(a);
m=strlen(s);

int p=-1;
f[0]=p;
for(int i=1;i<n;i++)
{
while(p!=-1 && a[p+1]!=a[i]) p=f[p];
if(a[p+1]==a[i]) p++;
f[i]=p;
}

for(int i=0;i<n;i++)
for(int j=0;j<52;j++)
{
char c=revh(j);
int p=i;
while(p!=-1 && a[p+1]!=c) p=f[p];
if(a[p+1]==c) p++;
tran[i][j]=p;
}

int cnt=0;

for(int i=0;i<m;i++) pre[i]=i-1;
state[-1]=-1;
int curp=-1;
for(int i=0;i<m;i++)
{
char c=s[i];

if(curp!=-1)
curp=tran[curp][ch(c)];
else
curp=( a[0]==c )-1;

state[i]=curp;

if(curp==n-1)
{
int p=i;
for(int j=0;j<n;j++)
{
s[p]=0;
p=pre[p];
}
curp=state[p];
pre[i+1]=p;
cnt++;
}
}

printf("%d\n",cnt);

return 0;
}

0

雨，纷飞 LV 8 @ 2013-07-30 09:33:18

栈+Sunday算法优化
var a:string;
b:array[1..1000000] of char;
po:array['A'..'z'] of longint;
p,i,len,ans:longint;
flag:boolean;
procedure build;
var i:longint;
begin
fillchar(po,sizeof(po),0);
for i:=1 to len do
po[a[i]]:=i;
end;
begin
readln(a);p:=0;len:=length(a);ans:=0;
build;
while not seekeof do begin
inc(p);read(b[p]);
if p<len then continue;
flag:=true;
for i:=1 to len do
if a[i]<>b[p-len+i] then begin
flag:=false;break;
end;

if flag then begin inc(ans);p:=p-len;end
else begin

if not seekeof then begin

inc(p);read(b[p]);

if po[b[p]]=len then begin
flag:=true;
for i:=1 to len-1 do

if a[i]<>b[p-len+i] then begin
flag:=false;break;
end;
if flag then begin inc(ans);p:=p-len;end;
end
else if po[b[p]]=0 then begin
for i:=1 to len-1 do
if not seekeof then begin

inc(p);read(b[p]);
end;
end
else begin
for i:=1 to len-po[b[p]]-1 do

if not seekeof then begin
inc(p);read(b[p]);
end;
end;
end;
end;
end;
write(ans);
end.

0

黑暗之神-赵 LV 10 @ 2012-09-15 15:12:01

这个出错是怎么回事

foo.pas(11,1) Fatal: illegal character "'?" ($A1)

Fatal: Compilation aborted

Error: C:\FPC\2.6.0\bin\i386-win32\ppc386.exe returned an error exitcode (normal if you did not specify a source file to be compiled)

我的大体思路是边读入边判断，但改了好几次都是这个错误提示

0

JackDavid127 LV 10 @ 2010-03-08 23:34:40

我直接被这题噎住……

刚开始虔诚的看了半天Matrix67神牛的论文，又诚惶诚恐的写了半天KMP匹配，交了好几次最高分才90.我心一横，干脆最后检查改成朴素匹配，OmsAC……

数据未免也太……

0

xqlovexz LV 10 @ 2010-03-06 13:49:35

用KMP匹配注意要严格O（n）的算法否则会像我一样超时...

受curimit神牛启发后

第二次...我杯具的写了个链表...

然后0ms AC...

0

jacklv LV 10 @ 2009-11-06 07:22:03

不是我过了，是数据太水

0

blacksnow LV 10 @ 2009-11-04 21:47:25

水题...不可用pos....

0

hydqy LV 8 @ 2009-11-03 21:58:33

栈好强大

0

Veili LV 9 @ 2009-11-02 20:19:13

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 9ms

├ 测试数据 11：答案正确... 56ms

没有秒过，不过已经很努力了……

program p1425;

var

ch: char;

lb,l,tot: longint;

a,b: ansistring;

begin

readln(b);

lb:=length(b);

l:=0; tot:=0;

a:='';

while not eof do begin

read(ch);

inc(l);

a:=a+ch;

if (l>=lb) and (ch=b[lb]) then

if copy(a,l-lb+1,lb)=b then begin

inc(tot);

delete(a,l-lb+1,lb);

dec(l,lb);

end;

end;

writeln(tot);

readln;

end.

0

naneux LV 8 @ 2009-10-21 20:42:21

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 447ms

├ 测试数据 07：答案正确... 197ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 212ms

├ 测试数据 11：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1509ms

我写的太疵了，还是没有秒杀

0

huyuanming11 LV 10 @ 2009-10-05 21:13:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

只有25行啊！

0

jinyuming LV 7 @ 2009-08-27 19:59:28

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

├ 测试数据 11：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：20 有效耗时：0ms

VAR

a:string;

b:ansistring;

i,len,total:longint;

BEGIN

READLN(a);

len:=length(a);

READLN(b);

WHILE pos(a,b)0 DO

BEGIN

delete(b,pos(a,b),len);

inc(total);

END;

WRITELN(total);

END.

0

linheng LV 8 @ 2009-08-22 11:18:51

无奈，数据太弱。

0

zhangjing1 LV 8 @ 2009-08-17 09:29:37

这么简单的题目还要看题解!? 太垃圾的

,,,,,,,,,谁有题解啊正确的快给我啊

0

Zintch LV 8 @ 2009-08-17 14:53:01

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 228ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：269ms

var

t,c:string;

s:array [1..1000000] of char;

i,j,k,n,l:longint;

begin

read(c);

readln;

n:=length(c);

while not eof do

begin

inc(j);

read(s[j]);

if j>=n then

begin

for i:=j-n+1 to j do t:=t+s[i];

if t=c then

begin

inc(l);

for i:=j-n+1 to j do s[i]:=' ';

j:=j-n;

end;

end;

t:='';

end;

write(l);

end.

水题，26行AC,虽然不是秒杀，注意是用eof输入的。

0

谭立春 LV 8 @ 2009-08-16 21:23:37

某老牛的!!!1

var

stack : array[ 0 .. 600000 ] of char ;

s : string ;

ini : ansistring ;

len , n , m : longint ;

procedure init ;

begin

readln( s ) ;

n := length( s ) ;

readln( ini ) ;

m := length( ini ) ;

end ;

procedure ins( ch : char ) ;

begin

inc( len ) ;

stack[ len ] := ch ;

end ;

procedure del( l : longint ) ;

begin

dec( len , l ) ;

end ;

function check : boolean ;

var

i : longint ;

begin

for i := len downto len - n + 1 do

begin

;

if stack[ i ] s[ len - i + 1 ] then

exit( false ) ;

end ;

check := true ;

end ;

procedure main ;

var

i , sum : longint ;

ch : char ;

begin

init ;

sum := 0 ;

for i := m downto 1 do

begin

ch := ini[ i ] ;

ins( ch ) ;

if ch = s[ 1 ] then

if check then

begin

del( n ) ;

inc( sum ) ;

//writeln( sum ) ;

end ;

end ;

writeln( sum ) ;

end ;

Begin

main ;

end .

0

junfpc LV 8 @ 2009-08-02 11:15:02

一个一个字符读入，秒杀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

maa04 LV 10 @ 2009-08-01 02:25:45

水题……囧……

仨指针在那转来转去……

这是Dragon测的：编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 25ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 9ms├ 测试数据 10：答案正确... 25ms├ 测试数据 11：答案正确... 41ms-------------------------Accepted 有效得分：100 有效耗时：100ms //嗯，这个倒挺整齐。。。我说的是得分和耗时。。。

这是Puppy测的：编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms├ 测试数据 11：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms

同样的程序，咋差别那么大捏？整整100ms啊……

接下来说说我的方法，可能你们以后做我的题会用得上：首先，准备仨指针p,q,k。p用来标记a字符串，q用来标记b字符串，这两个是比较两个字符串异同用的。然后一个k，用来标记当前b串输入到第几个字符。接着，如果a[p]=b[k]且k>=length(a)，那么开始进行判断。一个while然后就是一个指针移动的子串判断……接着就是一个异常退出的处理（这个等你们指针中途结束判断有误时再考虑）最后就是一个delete并且增加ans，再将指针k移动到当前q所在位置。输出ans即可。

0

我是姜逸伦大神 LV 8 @ 2009-07-17 16:48:20

水题

堆栈 0MS

题解

68 条题解

子串清除

信息

状态

开发

支持

题解

68 条题解

子串清除

信息

状态

开发

支持

还没有账户？

登录