Pagini recente » Cod sursa (job #1193957) | Cod sursa (job #1347761) | Cod sursa (job #2730730) | Cod sursa (job #2334287) | Cod sursa (job #1953958)
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[Nmax],B[Nmax];
int P[Nmax],q,N,M,sol[1005],n;
void Read()
{
fin.getline(A+1,Nmax);
fin.getline(B+1,Nmax);
A[0]=B[0]=' ';
N = strlen(A); N--;
M = strlen(B); M--;
}
void Precalculate()
{
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 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)
{
q=P[q];
n++;
if(n<=1000)
sol[n]=i-N;
}
}
}
void Print()
{
fout<<n<<"\n";
for(int i=1; i<=min(n,1000); i++)
fout<<sol[i]<<" ";
}
int main()
{
Read();
Precalculate();
KMP();
Print();
return 0;
}