Pagini recente » Cod sursa (job #3161684) | Cod sursa (job #1420856) | Cod sursa (job #1258701) | Cod sursa (job #2544769) | Cod sursa (job #1149524)
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>
#define nmax 2000002
using namespace std;
char t[nmax],p[nmax];
long long pi[nmax];
vector<int> sol;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long n,m;
void COMPUTE_PREFIX_FUNCTION()
{
pi[1]=0;
long long k=0,i;
for(i=2;i<=m;i++)
{
while(k>0 && p[k+1] != p[i])
k=pi[k];
if(p[k+1]==p[i])
k++;
pi[i] = k;
}
}
void kmp_match()
{
long long q,i;
COMPUTE_PREFIX_FUNCTION();
q=0;
for(i=1;i<=n;i++)
{
while(q>0 && p[q+1] != t[i])
q=pi[q];
if(p[q+1]==t[i])
q++;
if(q==m)
{
sol.push_back(i-m);
q=pi[q];
}
}
}
int main()
{
f.getline(p,nmax);
f.getline(t,nmax);
long long i;n=strlen(t);m=strlen(p);
for (i = m; i; i--) p[i] = p[i-1]; p[0] = ' ';
for (i = n; i; i--) t[i] = t[i-1]; t[0] = ' ';
kmp_match();
g<<sol.size()<<'\n';
for(i=0;i<min(1000,sol.size());i++)
g<<sol[i]<<' ';
f.close();g.close();
return 0;
}