Pagini recente » Cod sursa (job #656378) | Cod sursa (job #789267) | Cod sursa (job #3041308) | Cod sursa (job #325308) | Cod sursa (job #604717)
Cod sursa(job #604717)
#include <iostream>
#include <string>
#define LMax 2000005
using namespace std;
char A[LMax], B[LMax];
int N, M, Pi[LMax], NMatch, Match[1005];
void Read ()
{
freopen ("strmatch.in", "r", stdin);
scanf ("%s\n%s", &A, &B);
N=strlen (A);
M=strlen (B);
for (int i=N; i>0; --i)
{
A[i]=A[i-1];
}
for (int i=M; i>0; --i)
{
B[i]=B[i-1];
}
}
void Print ()
{
freopen ("strmatch.out", "w", stdout);
printf ("%d\n", NMatch);
for (int i=0; i<1000 and i<NMatch; ++i)
{
printf ("%d ", Match[i]);
}
printf ("\n");
}
void BuildPi ()
{
int k=0;
Pi[1]=0;
for (int i=2; i<=N; ++i)
{
while (k>0 and A[k+1]!=A[i])
{
k=Pi[k];
}
if (A[i]==A[k+1])
{
++k;
}
Pi[i]=k;
}
}
void KMP ()
{
int k=0;
BuildPi ();
for (int i=1; i<=M; ++i)
{
while (k>0 and B[i]!=A[k+1])
{
k=Pi[k];
}
if (B[i]==A[k+1])
{
++k;
}
if (k==N)
{
if (NMatch<1000)
{
Match[NMatch++]=i-N;
}
else
{
NMatch++;
}
}
}
}
int main()
{
Read ();
KMP ();
Print ();
return 0;
}