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