Pagini recente » Cod sursa (job #3039432) | Cod sursa (job #1368699) | Cod sursa (job #1545130) | Cod sursa (job #2886633) | Cod sursa (job #2283031)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int n = 0, m = 0, phiA[NMAX], v[1005];
char a[NMAX], b[NMAX];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.get(a + 1, NMAX);
fin.get();
fin.get(b + 1, NMAX);
n = (int)strlen(a + 1);
m = (int)strlen(b + 1);
a[n + 1] = ' ';
//construct phiA
int k = 0;
phiA[1] = 0;
for (int i = 2; i<=n; ++i)
{
while (k > 0 && a[i] != a[k + 1])
k = phiA[k];
if (a[i] == a[k + 1])
++k;
phiA[i] = k;
}
//construct phiB
k = 0;
int cnt = 0;
for (int i = 1; i<=m; ++i)
{
while (k > 0 && a[k + 1] != b[i])
k = phiA[k];
if (a[k + 1] == b[i])
++k;
if (k == n){
if (cnt < 1000)v[++cnt] = i;
else cnt++;}
}
fout << cnt << '\n';
for (int i = 1; i<=min(cnt , 1000); ++i)
fout << v[i] - n << " ";
fout << '\n';
return 0;
}