Pagini recente » Cod sursa (job #2247940) | Cod sursa (job #2572731) | Cod sursa (job #1397954) | Cod sursa (job #588046) | Cod sursa (job #1389918)
#include <fstream>
#include <cstring>
#define TMAX 2000004//100000
#define PMAX 2000004//1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m;
char T[TMAX], P[PMAX];
int prefix[PMAX];
int match[PMAX], nrmatch;
void citire();
void calcul_prefix();
void KMP();
void afisare();
int main()
{
citire();
calcul_prefix();
KMP();
afisare();
return 0;
}
void citire()
{
//fin>>n>>m;
fin>>P+1>>T+1;
n=strlen(T+1);
m=strlen(P+1);
}
void calcul_prefix()
{
int p, k;
prefix[1]=0;
for(p=2;p<=m;++p)
{
k=prefix[p-1];
while(k>0 && P[k+1]!=P[p])
k=prefix[k];
if(P[k+1]==P[p])
++k;
prefix[p]=k;
}
}
void KMP()
{
int t, k=0;
for(t=1;t<=n;++t)
{
while(k>0 && P[k+1]!=T[t])
k=prefix[k];
if(P[k+1]==T[t])
++k;
if(k==m)
{
match[++nrmatch]=t-m;
k=prefix[k];
}
}
}
void afisare()
{
int i;
fout<<nrmatch<<'\n';
for(i=1;i<=nrmatch;++i)
fout<<match[i]<<' ';
}