Pagini recente » Cod sursa (job #807806) | Cod sursa (job #976753) | Cod sursa (job #1627011) | Cod sursa (job #2525641) | Cod sursa (job #2175110)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e6 + 5;
char a[2 * MAXN + 1], b[MAXN + 1];
int z[2 * MAXN + 1];
vector <int> sol;
int main() {
FILE *fi, *fout;
int i;
fi = fopen("strmatch.in" ,"r");
fout = fopen("strmatch.out" ,"w");
fgets(a + 1, MAXN, fi);
fgets(b + 1, MAXN, fi);
int sza = strlen(a + 1) - 1, szb = strlen(b + 1) - 1;
int sz = sza + szb;
for(i = 1; i <= szb; i++) {
a[i + sza] = b[i];
}
int l = 0, r = 0;
z[1] = sz;
for(i = 2; i <= sz; i++) {
if(r >= i) {
z[i] = min(z[i - l + 1], r - i + 1);
}
while(i + z[i] <= sz && a[z[i] + 1] == a[i + z[i]])
z[i]++;
if(i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
int cnt = 0;
for(i = sza + 1; i <= sz; i++) {
if(z[i] >= sza) {
cnt++;
if(cnt <= 1000) {
sol.push_back(i - sza - 1);
}
}
}
fprintf(fout,"%d\n" ,cnt);
for(auto it : sol) {
fprintf(fout,"%d " ,it);
}
fclose(fi);
fclose(fout);
return 0;
}