Pagini recente » Cod sursa (job #2077361) | Cod sursa (job #1745371) | Cod sursa (job #2079378) | Cod sursa (job #2783524) | Cod sursa (job #2383779)
#include<bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
int lps[2000002];
vector<int>ans;
int main()
{
fin >> a >> b;
int n = a.size(), m = b.size();
int l = 0, i = 1;
lps[0] = 0;
while (i < n) {
if (a[i] == a[l]) {
l++;
lps[i] = l;
i++;
}
else {
if (l != 0)
l = lps[l - 1];
else {
lps[i] = 0;
i++;
}
}
}
i = 0;
int j = 0;
while (i < m) {
if (a[j] == b[i]) {
i++;
j++;
}
if (j == n) {
ans.push_back(i - j);
j = lps[j - 1];
}
else if (i < m && a[j] != b[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
fout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++)
fout << ans[i] << " ";
return 0;
}