Pagini recente » Cod sursa (job #2651779) | Cod sursa (job #2888138) | Cod sursa (job #2523901) | Cod sursa (job #252788) | Cod sursa (job #1135222)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define lmax 2000002
#define cout g
char p[lmax],text[lmax];
int ff[lmax];
int n,m,nr;
void make_prefix()
{
int i,v;
for(i=2;i<=n;++i)
{
v=i-1;
while (p[i]!=p[ff[v]+1] && v) v=ff[v];
if(p[i]==p[ff[v]+1]) ff[i]=ff[v]+1;
}
}
vector <int> sol;
void kmp()
{
int i,j(0);
for(i=1;i<=m;++i)
{
while (text[i]!=p[j+1] && j) j=ff[j];
if(text[i]==p[j+1])++j;
if(j==n)
{
if(sol.size()<=1000) sol.push_back(i-n);
j=ff[j];
++nr;
}
}
}
int main()
{
f>>p+1;
f>>text+1;
n=strlen(p+1);m=strlen(text+1);
make_prefix();
//for(int i=1;i<=n;++i)cout<<ff[i]<<' ';
kmp();
cout<<nr<<'\n';
for(int i=0;i<min((int)sol.size(),1001);++i)cout<<sol[i]<<' ';
return 0;
}