Pagini recente » Cod sursa (job #24650) | Cod sursa (job #2619849) | Cod sursa (job #1233626) | Cod sursa (job #1543453) | Cod sursa (job #2550720)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char t[N], p[N]; ///t - text, p - pattern
int a[N]; ///pozitiile fiecarei aparitii
int urm[N];
int n, m, k;
void Prefix()
{
int j=0;
for (int i=1; i<n; ++i)
{
while (j>0 && p[i]!=p[j])
j=urm[j-1];
if (p[i]==p[j]) j++;
urm[i]=j;
}
}
void KMP()
{
int q=0;
for (int i=0; i<m; ++i)
{
while (q>0 && p[q]!=t[i])
q=urm[q-1];
if (p[q]==t[i]) q++;
if (q==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]<<' ';
fout<<'\n';
fout.close();
}
int main()
{
fin.getline(p, N);
fin.getline(t, N);
fin.close();
n=strlen(p);
m=strlen(t);
Prefix();
KMP();
Afisare();
return 0;
}