Pagini recente » Cod sursa (job #3173515) | Cod sursa (job #1402218) | Cod sursa (job #3145572) | Cod sursa (job #2500203) | Cod sursa (job #1810637)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005],B[2000005];
int sol[1005],q,N,M,cont,p[2000005];
void read()
{
fin.getline(A+1,2000005);
fin.getline(B+1,2000005);
A[0]=' ';
B[0]=' ';
N=strlen(A)-1;
M=strlen(B)-1;
p[1]=0;
q=0;
for (int i = 2;i<=N;++i)
{
while(q && A[q+1]!=A[i])
q=p[q];
if (A[q+1]==A[i])
++q;
p[i]=q;
}
}
void solve()
{
int q=0;
for(int i=1;i<=M;i++)
{
while(q && A[q+1]!=B[i])
q=p[q];
if(A[q+1]==B[i])
q++;
if(q==N)
{
q=p[N];
cont++;
if(cont<=1000)
sol[cont]=i-N;
}
}
fout<<cont<<"\n";
for(int i=1;i<=min(cont,1000);++i)
fout<<sol[i]<<" ";
}
int main()
{
read();
solve();
return 0;
}