Pagini recente » Cod sursa (job #2218200) | Cod sursa (job #2278911)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string N,M;
int D[2000010],n,j,i,m,q,rez[2000010],k=0;
int main()
{
fin>>N>>M;
n=N.size();
j=-1;
D[0]=-1;
for(i=1; i<n; i++)
{
while(j>-1&&N[j+1]!=N[i])
j=D[j];
if(N[j+1]==N[i])
j++;
D[i]=j;
}
m=M.size();
q=-1;
for(i=0; i<m&&k<=1000; i++)
{
while(q>-1&&N[q+1]!=M[i])
q=D[q];
if(N[q+1]==M[i])
q++;
if(q==n-1)
{
k++;
rez[k]=i-n+1;
}
}
fout<<k<<'\n';
for(i=1;i<=k;i++)
{
fout<<rez[i]<<' ';
}
}