Pagini recente » Cod sursa (job #2507458) | Cod sursa (job #2921602) | Cod sursa (job #2954122) | Cod sursa (job #2696077) | Cod sursa (job #2727555)
#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 = 1; dr < sl;)
if(small[st] == small[dr]) lps[dr++] = ++st;
else if(st) st = lps[st - 1];
else lps[st] = 0, ++dr;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>small>>big,
sl = strlen(small), bl = strlen(big),
generLps();
for(int i = 0, j = 0; 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);
}
int n = min(1000, (int)ans.size());
printf("%d\n", (int)ans.size());
for(int i = 0; i < n; ++i) printf("%d ", ans[i]);
return 0;
}