Pagini recente » Istoria paginii runda/stele/clasament | Rating Galbeaza Daniel (GalbeazaDaniel) | Cod sursa (job #1770329) | Cod sursa (job #1299447) | Cod sursa (job #1908929)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nMax = 2e6 + 2;
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 and match.size() + 1 <= 1000) {
match.push_back(i - 2 * a.size());
}
}
fout << match.size() << '\n';
for (const auto& itr : match)
fout << itr << ' ';
return 0;
}