Pagini recente » Cod sursa (job #1168720) | Cod sursa (job #896018) | Cod sursa (job #1460771) | Cod sursa (job #1477094) | Cod sursa (job #556042)
Cod sursa(job #556042)
#include<fstream>
using namespace std;
ifstream f; ofstream g;
string a,b; int n,m,t,l[2000005],v[1005];
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){
if(++i<=1000) v[i]=t-k;
k=l[k];
}
}
g<<i<<'\n';
for(j=1;j<=i;++j) g<<v[j]<<' ';
return 0;
}