Pagini recente » Cod sursa (job #181968) | Cod sursa (job #1244653) | Cod sursa (job #2792231) | Cod sursa (job #1501731) | Cod sursa (job #2720669)
#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();) {
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);
}
int n = min(n, (int)ans.size());
printf("%d\n", (int)ans.size());
for(int i = 0; i < n; ++i) printf("%d ", ans[i]);
return 0;
}