Pagini recente » Istoria paginii runda/simulare_11_12_2003 | Cod sursa (job #806985) | Istoria paginii runda/and | Cod sursa (job #2155406) | 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 << ' ';
}
}