Pagini recente » Cod sursa (job #407481) | Cod sursa (job #2813626) | Cod sursa (job #1035842) | Cod sursa (job #1835007) | Cod sursa (job #188978)
Cod sursa(job #188978)
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define MAX_N 2000001
string A1,A2;
int N1, N2;
int P[MAX_N], Sol[1002];
void read(void);
void make_prefix(void);
void kmp(void);
int main()
{
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
read();
make_prefix();
kmp();
}
void read()
{
char S[MAX_N];
gets(S);
A1 = string(S);
N1 = A1.size();
gets(S);
A2 = string(S);
N2 = A2.size();
}
void make_prefix()
{
int i, q = -1;
for(i = 1, P[0] = -1; i < N1; ++i)
{
while (q >=0 && A1[i] != A1[q+1])
q = P[q];
if(A1[i] == A1[q+1])
++q;
P[i] = q;
}
}
void kmp()
{
int i, q = -1, n = 0;
for(i = 0; i < N2; ++i)
{
while(q >=0 && A1[q + 1] != A2[i])
q = P[q];
if(A1[q + 1] == A2[i])
++q;
if(q == N1 - 1)
{
q = P[N1 - 1];
++n;
if(n < 1001)
Sol[n] = i - N1 + 1;
}
}
printf("%d\n", n);
for (i = 1; i <= min(n, 1000); ++i)
printf("%d ", Sol[i]);
}