Pagini recente » Cod sursa (job #96497) | Cod sursa (job #3144342) | Cod sursa (job #297094) | Cod sursa (job #2186062) | Cod sursa (job #2923480)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, s;
const int SMAX = 2e6 + 3;
int N;
int kmp[SMAX];
void KMP(string a)
{
int k = 0;
N = a.size() - 1;
kmp[1] = 0;
for(int i = 2; i <= N; ++i) {
while(k > 0 && a[k + 1] != a[i])
k = kmp[k];
if(a[k + 1] == a[i])
++k;
kmp[i] = k;
}
}
int main()
{
fin >> pattern >> s;
KMP ("$" + pattern + "$" + s);
int ans = 0;
vector < int > sol;
for(int i = pattern.size() + 2; i <= N; ++i)
if(kmp[i] == pattern.size())
++ans, sol.push_back(i - kmp[i] - 1 - pattern.size());
fout << ans << '\n';
for(auto it: sol)
fout << it << ' ';
fout << '\n';
return 0;
}