Pagini recente » Cod sursa (job #1823008) | Cod sursa (job #545632) | Istoria paginii runda/simulare-cartita-43/clasament | Cod sursa (job #1812034) | Cod sursa (job #1908936)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m;
string a, b, s;
vector<int>Kmp(const string &that) {
vector<int>pi(that.size(), -1);
for (int i = 1; i < that.size(); ++i) {
int j = pi[i - 1];
while (j >= 0 and that[j + 1] != that[i]) {
j = pi[j];
}
if (that[j + 1] == that[i])
j++;
pi[i] = j;
}
return pi;
}
int main() {
fin >> a >> b;
s = a + '$' + b;
auto pi = Kmp(s);
vector<int>match;
for (int i = a.size(); i < s.size(); ++i) {
if (pi[i] == a.size() - 1) {
match.push_back(i - 2 * a.size());
}
}
fout << match.size() << '\n';
for (int i = 0; i < min(1000, (int)match.size()); ++i)
fout << match[i] << ' ';
return 0;
}