Pagini recente » Cod sursa (job #2916030) | Cod sursa (job #1791107) | Cod sursa (job #2880293) | Cod sursa (job #2260240) | Cod sursa (job #535820)
Cod sursa(job #535820)
#include <cstdio>
#include <cstring>
#define NMAX 2000010
#define MMAX 2000010
#define MOD1 100003
#define MOD2 100019
#define P 122
#define FOR(i, a, b) for(int i = a ; i <= b ; i++)
int P1 = 1, P2 = 1;
int URM[MMAX];
char A[NMAX],B[MMAX];
int M, N;
int NR = 0;
int poz[NMAX];
int L[NMAX];
void citire()
{
gets(A + 1);
gets(B + 1);
M = strlen(A + 1);
while(!A[M] || A[M] == '\n' || A[M] == EOF)
M--;
N = strlen(B + 1);
while(!B[N] || B[N] == '\n' || B[N] == EOF)
N--;
}
void face_l()
{
int k;
FOR(i, 2, M)
{
k = L[i - 1];
while(k && A[k + 1] != A[i])
k = L[k];
if(A[k + 1] == A[i])
k++;
L[i] = k;
}
}
void comp()
{
int k = 0;
FOR(i, 1, N)
{
while(k && A[k + 1] != B[i])
k = L[k];
if(A[k + 1] == B[i])
k++;
if(k == M)
poz[++NR] = i - M;
}
}
void scrie()
{
printf("%d\n",NR);
for(int i = 1 ; i <= NR && i <= 1000 ; i++)
printf("%d ",poz[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
face_l();
comp();
scrie();
return 0;
}