Pagini recente » Cod sursa (job #385226) | Cod sursa (job #1294605) | Cod sursa (job #2936960)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax=2e6+5;
int n,m,rasp;
char A[nmax],B[nmax];
int kmp[nmax];
int solutii[1003];
inline void indexFromOne()
{
while(A[n]!=0) n++;
while(B[m]!=0) m++;
for(int i=n; i>0; i--) A[i]=A[i-1];
A[0]=0;
for(int i=m; i>0; i--) B[i]=B[i-1];
B[0]=0;
}
inline void make_prefix()
{
int q=0;
kmp[1]=0;
for(int i=2; i<=n; i++)
{
while(q && A[q+1] != A[i]) q=kmp[q];
if(A[q+1] == A[i]) q++;
kmp[i]=q;
}
}
int main()
{
fin>>A>>B;
indexFromOne();
make_prefix();
int q=0;
for(int i=1; i<=m; i++)
{
while(q && A[q+1] != B[i]) q=kmp[q];
if(A[q+1] == B[i]) q++;
if(q==n)
{
q=kmp[n];
rasp++;
if(rasp<=1000)
solutii[rasp]=i-n;
}
}
fout<<rasp<<"\n";
for(int i=1; i<=min(rasp,1000); i++) fout<<solutii[i]<<" ";
fout<<"\n";
return 0;
}