Pagini recente » Clasament pieceofshit | Cod sursa (job #1849400) | Cod sursa (job #3159035) | Cod sursa (job #275651) | Cod sursa (job #2860607)
#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 (i < slen) {
if (p[j] == s[i]) i++, j++;
if (j == plen) add(i - j), 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 << ' ';
}