Pagini recente » Cod sursa (job #1040295) | Cod sursa (job #844922) | Cod sursa (job #1473042) | Cod sursa (job #2297336) | Cod sursa (job #2860403)
#include <iostream>
#include <cstring>
#include <vector>
#define nmax 2000001
using namespace std;
static int plen, slen, count;
static char p[nmax], s[nmax];
static int lps[nmax];
vector<int> ans;
inline void add(int index) {
if (ans.size() < 1000U)
ans.push_back(index);
count++;
}
inline void search() {
int i = 0, j = 0;
while (j < slen) {
if (p[i] == s[j]) i++, j++;
if (j == plen) add(i), j = lps[j - 1];
else if (i < slen && p[j] != s[i])
j ? j = lps[j - 1] : i++;
}
}
inline void computeLps() {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < plen) {
if (p[i] == p[len]) lps[i++] = ++len;
else if (len) len = lps[len-1];
else lps[i++] = 0;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> p >> s;
plen = strlen(p);
slen = strlen(s);
computeLps();
search();
cout << count << endl;
for (int k : ans) cout << k << ' ';
}