Pagini recente » Cod sursa (job #1963392) | Cod sursa (job #1006224) | Cod sursa (job #182131) | Cod sursa (job #3154253) | Cod sursa (job #2105799)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
void Solve (string s, int l) {
int o = -1, r = -1, ans = 0, sz = (int) s.size ();
vector < int > z (sz + 1), sol;
for (int i = 2; i < sz; ++ i) {
if (i >= r) {
++ z[i];
while (i + z[i] - 1 < sz and s[i + z[i] - 1] == s[z[i]]) {
++ z[i];
}
-- z[i];
o = i;
r = i + z[i] - 1;
if (z[i] == l) {
++ ans;
sol.push_back (i - l - 2);
}
continue;
}
int k = z[i - o + 1];
if (i + k - 1 <= r) {
z[i] = k;
if (z[i] == l) {
++ ans;
sol.push_back (i - l - 2);
}
continue;
}
z[i] = r - i + 1;
while (i + z[i] - 1 < sz and s[i + z[i] - 1] == s[z[i]]) {
++ z[i];
}
-- z[i];
o = i;
r = i + z[i] - 1;
if (z[i] == l) {
++ ans;
sol.push_back (i - l - 2);
}
}
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 ());
}