Pagini recente » Cod sursa (job #2006991) | Cod sursa (job #1817823) | Cod sursa (job #2938475) | Cod sursa (job #3352188) | Cod sursa (job #2222966)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
unsigned int p[2000009];
vector < size_t > v;
void f(string & s) {
s = '!' + s;
unsigned int k = 0;
for(size_t i = 2; i < s.size(); ++i) {
while (k && s[k + 1] != s[i]) {
k = p[k];
}
if (s[k + 1] == s[i]) {
p[i] = ++k;
}
else {
k = 0;
}
}
}
string a, b;
int main() {
cin >> a >> b;
a = a + '!' + b;
f(a);
for (size_t i = a.size() - b.size() + 1; i < a.size(); ++i) {
if (p[i] == a.size() - b.size() - 2) {
v.push_back(i - a.size() + b.size() - 2);
}
}
cout << v.size() << '\n';
for (auto i : v) {
cout << i << ' ';
}
}