Pagini recente » Cod sursa (job #1127524) | Cod sursa (job #2833980) | Cod sursa (job #1544818) | Cod sursa (job #1743941) | Cod sursa (job #2425849)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define LMAX 2000002
using namespace std;
char txt[LMAX], pat[LMAX], pi[LMAX];
int n, m, nsol, sol[1001];
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[q];
++nsol;
sol[nsol] = i - m;
}
}
fout << nsol <<'\n';
for(int i = 1; i<=nsol; i++)
fout << sol[i] <<' ';
}