Pagini recente » Cod sursa (job #1482984) | Cod sursa (job #2425083)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define LMAX 2000002
using namespace std;
char pat[LMAX], txt[LMAX];
int pi[LMAX], sol[1001], n, m, nsol;
void make_prefix()
{
int k = 0;
pi[1] = 0;
for(int i = 2; i<=m; ++i)
{
while(k > 0 && pat[k+1] != pat[i]) k = pi[k];
if(pat[k+1] == pat[i]) ++k;
pi[i] = k;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> (pat + 1);
fin >> (txt + 1);
m = strlen(pat + 1);
n = strlen(txt + 1);
make_prefix();
int j = 0;
for(int i = 1; i<=n; i++)
{
while(j > 0 && txt[i] != pat[j+1]) j = pi[j];
if(txt[i] == pat[j+1]) j++;
if(j == m)
{
j = pi[m];
++nsol;
if(nsol <=1000) sol[nsol] = i - m;
}
}
fout << nsol << endl;
for(int i = 1; i<=min(nsol, 1000); i++)
fout << sol[i] <<' ';
}