Pagini recente » Cod sursa (job #985975) | Cod sursa (job #2272708) | Cod sursa (job #209384) | Cod sursa (job #2774116) | Cod sursa (job #1349195)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 2000002
char a[MAXN];
char b[MAXN];
int N, alen, blen;
int pref[MAXN];
vector<int> matches;
void computePref()
{
int i, k = 0;
pref[1] = 0;
for (i = 2 ; i <= alen ; ++i)
{
while (k > 0 && a[k+1] != a[i])
k = pref[k];
if (a[k+1] == a[i])
k++;
pref[i]=k;
}
}
void kmp()
{
int i, k = 0;
for (i = 1 ; i <= blen ; ++i)
{
while (k > 0 && b[i] != a[k + 1])
k = pref[k];
if (b[i] == a[k+1])
k++;
if (k == alen) // we've got a match
{
N++;
if (N < 1000)
{
matches.push_back(i - alen);
}
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", a+1);
scanf("%s", b+1);
alen = strlen(a + 1);
blen = strlen(b + 1);
computePref();
kmp();
printf("%d\n", N);
for (vector<int>::iterator it = matches.begin() ; it != matches.end() ; ++it)
printf("%d ", *it);
printf("\n");
return 0;
}