Pagini recente » Cod sursa (job #2880752) | Cod sursa (job #707092) | Cod sursa (job #2076163) | Cod sursa (job #2210092) | Cod sursa (job #1998711)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005],B[2000005];
int n,m;
int urm[2000005];
int V[1024];
int w;
void urmatorul()
{
int k=-1;
urm[0]=0;
for(int x=1;x<m;++x)
{
while(k>0 && A[k+1]!=A[x]) k=urm[k];
if(A[k+1]==A[x]) k++;
urm[x]=k;
}
}
int main()
{ int x=-1;
f.getline(A,2000005);
f.getline(B,2000005);
n=strlen(B);
m=strlen(A);
urmatorul();
for(int i=0;i<n;++i)
{
while(x>0 && A[x+1]!=B[i]) x=urm[x];
if(A[x+1]==B[i]) x++;
if(x==m-1)
{
++w;
if(w<=1000)
V[w]=i-m+1;
x=urm[x];
}
}
g<<w<<'\n';
for(int i=1;i<=min(w,1000);++i)
g<<V[i]<<" ";
return 0;
}