Pagini recente » Cod sursa (job #2863632) | Cod sursa (job #36975) | Cod sursa (job #1340616) | Cod sursa (job #2334317) | Cod sursa (job #556024)
Cod sursa(job #556024)
#include<fstream>
using namespace std;
ifstream f; ofstream g;
string a,b; int k,p,n,m,t,l[2000005],v[2000005];
void prefix(){
l[1]=0;
for(p=2;p<=m;++p){
k=l[p-1];
while(k&&a[k+1]!=a[p]) k=l[k];
if(a[k+1]==a[p]) ++k;
l[p]=k;
}
}
int main(){
int i;
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();
k=0;
i=0;
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){
v[++i]=t-k;
k=l[k];
}
}
g<<i<<'\n';
for(int j=1;j<=i;++j) g<<v[j]<<' ';
return 0;
}