Pagini recente » Cod sursa (job #1963538) | Cod sursa (job #496727) | Cod sursa (job #703653) | Cod sursa (job #1947564) | Cod sursa (job #556087)
Cod sursa(job #556087)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f; ofstream g;
string a,b; int n,m,t,l[2000010],v[1010];
void prefix(){
int p,k=0;
for(p=2,l[1]=0;p<=m;++p){
while(k&&a[k+1]!=a[p]) k=l[k];
if(a[k+1]==a[p]) ++k;
l[p]=k;
}
}
int main(){
int j,i=0,k=0;
f.open("strmatch.in"); g.open("strmatch.out");
f>>a>>b;
m=a.length(); n=b.length();
for(i=m;i;--i) a[i]=a[i-1]; a[0]=' ';
for(i=n;i;--i) b[i]=b[i-1]; b[0]=' ';
prefix();
for(t=1;t<=n;++t){
while(k&&a[k+1]!=b[t]) k=l[k];
if(a[k+1]==b[t]) ++k;
if(k==m){
k=l[k];
if(++i<=1000) v[i]=t-m;
}
}
g<<i<<'\n';
for(j=1;j<=min(i,1000);++j) g<<v[j]<<' ';
return 0;
}