Pagini recente » Cod sursa (job #1037154) | Cod sursa (job #2209798) | Cod sursa (job #2078050) | Cod sursa (job #1556202) | Cod sursa (job #1954911)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax=2000005;
int N,M,q,P[NMax],Sol[1005],k;
char A[NMax],B[NMax];
void Read()
{
fin.getline(A+1,NMax);
fin.getline(B+1,NMax);
A[0]=B[0]=' ';
N = strlen(A);
M = strlen(B);
N--;
M--;
}
void Make_prefix()
{
for(int i=2;i<=N;++i)
{
while(q && A[i]!=A[q+1])
{
q=P[q];
}
if(A[i]==A[q+1])
{
q++;
}
P[i]=q;
}
}
void KMP()
{
q=0;
for(int i=1;i<=M;++i)
{
while(q && B[i]!=A[q+1])
{
q=P[q];
}
if(B[i]==A[q+1])
{
q++;
}
if(q==N)
{
k++;
if(k<=1000)
{
Sol[k]=i-N;
}
q=P[q];
}
}
fout<<k<<"\n";
for(int i=1;i<=k;++i)
{
fout<<Sol[i]<<" ";
}
fout<<"\n";
}
int main()
{
Read();
Make_prefix();
KMP();
return 0;
}