Pagini recente » Cod sursa (job #2097593) | Cod sursa (job #2750535) | Cod sursa (job #522102) | Cod sursa (job #2233280) | Cod sursa (job #2462007)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int n, l, r, ans;
int zet[4000005], v[1005];
string s1, s2, s;
int main() {
fin >> s1 >> s2;
s = '#' + s1 + '#' + s2;
n = s1.size() + s2.size() + 1;
zet[1] = 1;
for (int i = 2; i <= n; ++i) {
if (i >= r) {
l = i;
int x = 1;
while (s[i + x - 1] == s[x] && i + x - 1 <= n)
++x;
--x;
r = i + x - 1;
zet[i] = x;
if (x == s1.size()) {
++ans;
if (ans <= 1000)
v[ans] = i - s1.size() - 2;
}
continue;
}
if (i + zet[i - l + 1] >= r) {
int x = r - i + 1;
while (s[i + x - 1] == s[x] && i + x - 1 <= n)
++x;
--x;
r = i + x - 1;
zet[i] = x;
if (x == s1.size()) {
++ans;
if (ans <= 1000)
v[ans] = i - s1.size() - 2;
}
l = i;
continue;
}
zet[i] = zet[i - l + 1];
if (zet[i] == s1.size()) {
++ans;
if (ans <= 1000)
v[ans] = i - s1.size() - 2;
}
}
fout << ans << '\n';
for (int i = 1; i <= min(ans, 1000); ++i)
fout << v[i] << ' ';
return 0;
}