Pagini recente » Cod sursa (job #835792) | Cod sursa (job #773729) | Cod sursa (job #1760528) | Cod sursa (job #664846) | Cod sursa (job #2105859)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
void Solve (string s, int l) {
int sz = (int) s.size (), ans = 0;
vector < int > kmp (sz), sol;
sol.reserve (1000);
for (int i = 2; i < sz; ++ i) {
int k = kmp[i - 1];
while (k != 0) {
if (s[k + 1] == s[i]) {
break;
}
k = kmp[k];
}
s[k + 1] == s[i] ? (kmp[i] = k + 1) : (kmp[i] = k);
if (kmp[i] == l) {
++ ans;
if (sol.size () < 1000) {
sol.emplace_back (i - (2 * l) - 1);
}
}
}
cout << ans << '\n';
for (auto x : sol) {
cout << x << ' ';
}
cout << '\n';
}
int main () {
ios::sync_with_stdio (false);
string s1, s2;
cin >> s1 >> s2;
s2 = ' ' + s1 + '#' + s2;
Solve (s2, (int) s1.size ());
}