Pagini recente » Istoria paginii runda/testac | Cod sursa (job #129983) | Monitorul de evaluare | Cod sursa (job #1889189) | Cod sursa (job #2222995)
#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() {
int o1000(1000);
cin >> a >> b;
int orga = a.size();
a = a + '!' + b;
f(a);
for (size_t i = a.size() - b.size(); i < a.size(); ++i) {
if (p[i] == orga && o1000) { /// - original a.size() + 1 bcz we want the start poz
v.push_back(i - orga - orga - 1);
--o1000;
}
}
cout << v.size() << '\n';
for (auto i : v) {
cout << i << ' ';
}
}