Pagini recente » Cod sursa (job #2518192) | Cod sursa (job #2905801) | Cod sursa (job #1171707) | Cod sursa (job #2560692) | Cod sursa (job #2266805)
#include <bits/stdc++.h>
#define Nmax 40000009
using namespace std;
#define USE_FILES 1
#ifdef USE_FILES
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
#endif // USE_FILES
int z[Nmax];
string a,b;
char P[Nmax];
int s[1004];
void strbuild(string a, string b) {
int l1 = a.size();
int l2 = b.size();
for (int i = 0; i < l1; ++i) {
P[i + 1] = a[i];
}
P[l1+1] = '#';
for (int i = 0; i < l2; ++i) {
P[l1 + i + 2] = b[i];
}
}
void Z(char P[Nmax], int n) {
z[1] = 0;
int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
if (i <= r) {
z[i] = min(z[i - l], r - i + 1);
}
while (i + z[i] - 1 <= n && P[i + z[i]] == P[z[i] + 1]) {
++z[i];
}
if (i + z[i] - 1 >= r) {
r = i + z[i] -1;
l = i;
}
}
}
int main() {
cin >> a >> b;
int l1 = a.size();
int l2 = b.size();
strbuild(a, b);
int n = l1 + l2 +1;
// for (int i = 1; i <= n; ++i) cout << P[i];
Z(P, n);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (z[i] == l1) {
++cnt;
if (cnt <= 1000) s[cnt] = i;
//if (cnt == 1000) break;
}
}
cout << cnt << '\n';
cnt = min (cnt, 1000);
for (int i = 1; i <= cnt; ++i) {
cout << s[i] - l1 - 2 << ' ';
}
return 0;
}