Pagini recente » Cod sursa (job #1078620) | Cod sursa (job #3228024) | Cod sursa (job #2889594) | Cod sursa (job #1405885) | Cod sursa (job #2759672)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 2e6 + 2;
char a[N];
char b[N];
int lps[N];
int s[1001];
void calc_lps(){
lps[0] = 0;
int i = 1, len = 0;
while (b[i] != 0){
if (b[i] == b[len]){
len++;
lps[i] = len;
i++;
}
else{
if (len != 0)
len = lps[len-1];
else{
lps[i] = 0;
i++;
}
}
}
//for (int i=0; b[i] != 0; i++)
//printf("%d ", lps[i]);
//printf("\n");
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(b, N, stdin);
fgets(a, N, stdin);
b[strlen(b)-1] = 0;
char * enda = &a[strlen(a)-1];
if (*enda == '\n') *enda = 0;
calc_lps();
int i=0, j=0, sn = 0;
while (a[i] != 0)
{
if (a[i] == b[j]){
i++;
j++;
}
else {
if (j == 0)
i++;
else
j = lps[j-1];
}
if (b[j] == 0){
if (sn < 1000)
s[sn] = i - j;
sn++;
}
}
printf("%d\n", sn);
for (int i=0; i<sn && i<1000; i++)
printf("%d ", s[i]);
}
/*
ABA
CABBCABABAB
*/