Pagini recente » Cod sursa (job #2683677) | Cod sursa (job #98244) | Cod sursa (job #2694748) | Cod sursa (job #1712341) | Cod sursa (job #1242362)
#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];
if(A[i] == A[aux])
pi[i] = aux + 1;
else
pi[i] = 0;
}
}
void solve()
{
int pos = 0, j = 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;
}