Pagini recente » Cod sursa (job #2803316) | Cod sursa (job #2935586) | Cod sursa (job #2703236) | Cod sursa (job #1274003) | Cod sursa (job #2376165)
#include <iostream>
#include <fstream>
#include <string.h>
#define nmax 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char cuv[nmax+5],text[nmax+5];
int lps[nmax+5],poz[1005],m,n,nr;
void prelps()
{
int i=0,j=-1;
lps[0]=-1;
while(i<m)
{
while(j>=0 && cuv[i]!=cuv[j])
j=lps[j];
i++;
j++;
lps[i]=j;
}
}
int main()
{
fin>>cuv>>text;
m=strlen(cuv);
n=strlen(text);
prelps();
int i=0,j=0;
while(i<n)
{
while(j>=0 && cuv[j]!=text[i])
j=lps[j];
j++;
i++;
if(j==m)
{
j=lps[j];
nr++;
if(nr<=1000)
poz[nr]=i-m;
}
}
fout<<nr<<"\n";
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;i++)
fout<<poz[i]<<" ";
return 0;
}