Pagini recente » tema_3_iulie | Cod sursa (job #3234859) | Cod sursa (job #1091088) | Cod sursa (job #3252522) | Cod sursa (job #1242411)
#include <cstdio>
#define NMAX 2000001
using namespace std;
char A[NMAX], B[NMAX];
int pi[NMAX], lA, lB, count, position[1001];
int getLength(char *word)
{
int length = 0;
while(*word != '\0')
{
word++;
length++;
}
return length;
}
void read()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
lA = getLength(A);
scanf("%s", B);
lB = getLength(B);
}
void piCompute()
{
pi[0] = 0;
for(int i = 1; i < lA; i++)
{
int aux = pi[i-1];
while(A[i] != A[aux] && aux)
{
aux = pi[aux-1];
}
if(A[i] == A[aux])
aux++;
pi[i] = aux;
}
}
void solve()
{
int pos = 0;
for(int j = 0; j < lB; j++)
{
while(pos && B[j] != A[pos])
pos = pi[pos-1];
if(B[j] == A[pos])
pos++;
if(pos == lA)
{
if(count < 1001)
position[count] = j - lA + 1;
count++;
pos = pi[pos-1];
}
}
int a = count < 1001 ? count : 1000;
printf("%d\n", count);
for(int i = 0; i < a; i++)
printf("%d ", position[i]);
}
int main() {
read();
piCompute();
solve();
return 0;
}