Pagini recente » Cod sursa (job #3252677) | Cod sursa (job #2925352) | Cod sursa (job #670700) | Cod sursa (job #1511638) | Cod sursa (job #2861105)
///KMP
#include <cstring>
#include <fstream>
#define N (int)2e6+2
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char t[N], p[N];
int a[N], lps[N]; ///lps[i] - lungimea maxima a unei secvente ce
///este si prefix si sufix
int n, m, k;
void prefix()
{
lps[0]=0;
int j=0;
for (int i=1; i<n; ++i)
{
while (j>0 && p[i]!=p[j]) j=lps[j-1];
if (p[i]==p[j]) j++;
lps[i]=j;
}
}
void kmp()
{
int j=0;
for (int i=0; i<m; ++i)
{
while (j>0 && t[i]!=p[j]) j=lps[j-1];
if (t[i]==p[j]) j++;
if (j==n) a[++k]=i-n+1;
}
}
void afisare()
{
fout<<k<<'\n';
if (k>1000) k=1000;
for (int i=1; i<=k; ++i) fout<<a[i]<<' ';
}
int main()
{
fin.getline(p, N);
fin.getline(t, N);
n=strlen(p);
m=strlen(t);
prefix();
kmp();
afisare();
return 0;
}