Pagini recente » Cod sursa (job #3221950) | Cod sursa (job #2635710) | Cod sursa (job #3000378) | Cod sursa (job #546206) | Cod sursa (job #1991810)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
string problema = "strmatch";
ifstream in(problema+".in");
ofstream out(problema+".out");
int a,b,cnt,v[2000001];
char A[2000001],B[2000001];
int T[2000001];
void kmp_table()
{
int pos=1,cnd=0;
T[0]=-1;
while(pos<a)
{
if(A[pos]==A[cnd])
{
T[pos]=T[cnd];
pos++;cnd++;
}
else
{
T[pos]=cnd;
cnd=T[cnd];
while(cnd>=0 && A[pos]!=A[cnd])
{
cnd=T[cnd];
}
pos++;
cnd++;
}
}
T[pos]=cnd;
}
void kmp_search()
{
int m=0,i=0;
while(m+i<b)
{
if(A[i]==B[m+i])
{
i++;
if(i==a)
{
v[cnt++]=m;
m=m+i-T[i];
i=T[i];
}
}
else
{
if(T[i]>-1)
{
m=m+i-T[i];
i=T[i];
}
else
{
m=m+i+1;
i=0;
}
}
}
}
int main()
{
in>>A>>B;
a=strlen(A);
b=strlen(B);
kmp_table();
kmp_search();
out<<cnt<<'\n';
for(int i = 0;i<min(cnt,1000);i++)
{
out<<v[i]<<' ';
}
return 0;
}