Pagini recente » Cod sursa (job #863838) | Cod sursa (job #1333546) | Cod sursa (job #24997) | Cod sursa (job #2331376) | Cod sursa (job #1520327)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
char a[2000005],b[2000005];
int n,m,pi[12000005],rez[1024],N;
void citire()
{
ifstream f("strmatch.in");
f.getline(a,2000005);f.getline(b,2000005);
f.close();
n=strlen(a);
m=strlen(b);
}
void prefix()
{
int q=0,i;
for (i=2;i<=m;i++)
{
while (q>0&&b[q]!= b[i])
q=pi[q-1];
if (b[q]==b[i])
q++;
pi[i] = q;
}
}
void fct()
{
int q=0;
for(int i=1;i<=n;i++)
{
while(q>0 && b[q]!=a[i])
q=pi[q-1];
if(b[q]==a[i]) q++;
if(q==m)
{
q=pi[q];
N++;
rez[N]=i-m;
}
}
}
int main()
{
citire();
prefix();
fct();
ofstream g("strmatch.out");
g<<N<<endl;
for(int i=1;i<=N;i++)
g<<rez[i]<<" ";
return 0;
}