Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1092519) | Rezultatele filtrării | Cod sursa (job #2722223)
#include <fstream>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int n, k, ans;
int z[4000005];
string s1, s2, s;
void Z() {
int l = 1, r = 0;
for (int i = 2; i <= n; ++i) {
if (z[i - l + 1] + i <= r) {
z[i] = z[i - l + 1];
continue;
}
int x = 1;
if (i <= r)
x = r - i + 1;
while (x <= i && s[x] == s[i + x - 1])
++x;
--x;
z[i] = x;
if (i + x - 1 > r)
l = i;
r = i + x - 1;
}
}
int main() {
cin >> s1 >> s2;
k = s1.size();
s = "#" + s1 + "#" + s2;
n = s1.size() + s2.size() + 1;
Z();
for (int i = k + 1; i <= n; ++i)
if (z[i] == k)
++ans;
cout << ans << '\n';
int cnt = 0;
for (int i = k + 1; i <= n && cnt < 1000; ++i) {
if (z[i] == k) {
cout << i - k - 2 << ' ';
++cnt;
}
}
return 0;
}