Pagini recente » Cod sursa (job #154103) | Cod sursa (job #1126188) | Cod sursa (job #2409330) | Cod sursa (job #1496462) | Cod sursa (job #3274192)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
inline vector<int> prefix_function(string s) {
int n = s.size();
vector<int> pi(n);
for(int i=1; i<n; i++) {
int j = pi[i - 1];
while(j > 0 && s[i] != s[j]) j = pi[j - 1];
if(s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
inline vector<int> kmp(string a, string b) {
int n = b.size(), m = a.size();
vector<int> pi = prefix_function(a);
vector<int> rez;
int i = 0, j = 0;
while(i < n) {
if(b[i] == a[j]) {
i++, j++;
if(j == m) rez.push_back(i - j), j = pi[j - 1];
}
else {
if(j > 0) j = pi[j - 1];
else i++;
}
}
return rez;
}
int main()
{
fin >> a >> b;
vector<int> rez = kmp(a, b);
fout << rez.size() << '\n';
for(int i : rez) fout << i << " ";
return 0;
}