Pagini recente » Cod sursa (job #1063362) | Cod sursa (job #363893) | Cod sursa (job #363902) | Cod sursa (job #3215878) | Cod sursa (job #2791154)
#include <iostream>
#include <cstring>
using namespace std;
const int NMAX = 2000010;
int micl, marel, lps[NMAX + 1], ans[1010], ansl;
char mare[NMAX + 1], mic[NMAX + 1];
void generLps() {
lps[0] = -1;
for(int i = 0, j = -1; i < micl;) {
while(j >= 0 && mic[i] != mic[j])
j = lps[j];
lps[++i] = ++j;
}
}
void kmp() {
for(int i = 0, j = 0; i < marel;) {
while(j >= 0 && mare[i] != mic[j])
j = lps[j];
++i, ++j;
if(j == micl) {
j = lps[j];
if(++ansl <= 1000)
ans[ansl] = i - micl;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", mic, mare);
micl = strlen(mic), marel = strlen(mare);
generLps();
kmp();
printf("%d\n", ansl);
ansl = min(ansl, 1000);
for(int i = 1; i <= ansl; ++i)
printf("%d ", ans[i]);
return 0;
}