Pagini recente » Cod sursa (job #566283) | Cod sursa (job #2500368) | Cod sursa (job #2151919) | Cod sursa (job #556821) | Cod sursa (job #3170498)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir[2000001];
char subsir[2000001];
int patern[2000001];
int cnt;
int poz[1001];
int n,m;
void citire()
{
fin>>(subsir+1);
fin>>(sir+1);
m=strlen(sir+1);
n=strlen(subsir+1);
}
void getpatern()
{
int j = 0;
for(int i = 2; i <= n; i++)
{
while(j > 0 && subsir[i] != subsir[j + 1])
{
j = patern[j];
}
if(subsir[i] == subsir[j + 1])
{
j++;
}
patern[i] = j;
}
}
void kmp()
{
int j=1;
for(int i=1; i<=m; i++)
{
while(j>0 && subsir[j]!=sir[i])
{
j=patern[j-1]+1;
}
j++;
if(j==n+1)
{
poz[cnt++]=i-j+1;
j=patern[j-1]+1;
}
}
}
int main()
{
citire();
patern[0]=-1;
getpatern();
kmp();
fout<<cnt<<'\n';
for(int i=0; i<cnt && i<=1000; i++)
{
fout<<poz[i]<<" ";
}
return 0;
}