Pagini recente » Cod sursa (job #394879) | Cod sursa (job #977170) | Cod sursa (job #2057979) | Rating Rusu-Raiciu Andrei-Tiberiu (rusuandrei27) | Cod sursa (job #188963)
Cod sursa(job #188963)
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define MAX_N 2000001
string A1,A2;
int N1, N2;
int pr[MAX_N], pz[1002];
void read();
void make_prefix();
void str_match();
int main()
{
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
read();
make_prefix();
str_match();
}
void read()
{
char S[MAX_N];
gets(S);
A1 = string(S);
A1.insert(A1.begin(),' ');
N1 = A1.size() - 1;
gets(S);
A2 = string(S);
A2.insert(A2.begin(),' ');
N2 = A2.size() - 1;
}
void make_prefix()
{
int i, q = 0;
for(i = 2, pr[1] = 0; i <= N1; ++i)
{
while (q && A1[i] != A1[q+1])
q = pr[q];
if(A1[i] == A1[q+1])
++q;
pr[i] = q;
}
}
void str_match()
{
int i, q = 0, n = 0;
for(i = 1; i<=N2; ++i)
{
while(q && A1[q + 1] != A2[i])
q = pr[q];
if(A1[q + 1] == A2[i])
++q;
if(q == N1)
{
q = pr[N1];
++n;
if(n < 1001)
pz[n] = i - N1;
}
}
printf("%d\n", n);
for (i = 1; i <= min(n, 1000); ++i)
printf("%d ", pz[i]);
}