Pagini recente » Cod sursa (job #785464) | Cod sursa (job #2210909) | Cod sursa (job #1570356) | Cod sursa (job #1342022) | Cod sursa (job #2720659)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6;
int lps[NMAX + 1];
string pat, txt;
vector<int> ans;
void generLPS() {
lps[0] = 0;
for(int len = 0, i = 1; i < pat.length();)
if(pat[len] == pat[i])
lps[i] = len + 1,
++i, ++len;
else {
if(len != 0) len = lps[len - 1];
else lps[len] = 0, ++i;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>pat>>txt;
generLPS();
for(int i = 0, j = 0; i < txt.length() && ans.size() <= 1000;) {
if(txt[i] == pat[j]) ++i, ++j;
else {
if(j == 0) ++i;
else j = lps[j - 1];
}
if(j == pat.length()) ans.push_back(i - j);
}
printf("%d\n", (int)ans.size());
for(const auto el : ans) printf("%d ", el);
return 0;
}