Pagini recente » Cod sursa (job #906617) | Cod sursa (job #120674) | Cod sursa (job #2258037) | Cod sursa (job #2478630) | Cod sursa (job #2149910)
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
vector <int> a, b, pi, sol;
string s1, s2;
int main() {
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
cin >> s1 >> s2;
a.resize(s1.size() + 1);
b.resize(s2.size() + 1);
pi.resize(s1.size() + 1);
for (int i = 0; i < s1.size(); i++) {
a[i + 1] = s1[i];
}
for (int i = 0; i < s2.size(); i++) {
b[i + 1] = s2[i];
}
int k = 0;
for (int i = 2; i < a.size(); i++) {
while (k && a[k + 1] != a[i]) {
k = pi[k];
}
if (a[k + 1] == a[i]) {
k++;
}
pi[i] = k;
}
k = 0;
int sols = 0;
for (int i = 1; i < b.size(); i++) {
while (k && a[k + 1] != b[i]) {
k = pi[k];
}
if (a[k + 1] == b[i]) {
k++;
}
if (k == a.size() - 1) {
sols ++;
if (sol.size() <= 1000) {
sol.push_back(i - k);
}
k = pi[k];
}
}
cout << sols << "\n";
for (int i = 0; i < sol.size(); i++) {
cout << sol[i] << " " ;
}
return 0;
}