Pagini recente » Cod sursa (job #664395) | Cod sursa (job #1692793) | Cod sursa (job #2328385) | Cod sursa (job #1938906) | Cod sursa (job #2727549)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6;
int sl, bl, lps[NMAX + 3];
char small[NMAX + 3], big[NMAX + 3];
vector<int> ans;
void generLps() {
lps[0] = 0;
for(int st = 0, dr = 2; dr < sl;)
if(small[st] == small[dr]) lps[dr++] = ++st;
else if(st) st = lps[st - 1];
else lps[dr++] = 0;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", small, big),
sl = strlen(small), bl = strlen(big),
generLps();
for(int i = 1, j = 1; i < bl;) {
if(big[i] == small[j]) ++i, ++j;
else if(j) j = lps[j - 1];
else ++i;
if(j == sl) ans.push_back(i - j), j = lps[j - 1];
}
printf("%d\n", (int)ans.size());
for(const auto el : ans) printf("%d ", el);
return 0;
}