Pagini recente » Cod sursa (job #976853) | Cod sursa (job #1636057) | Cod sursa (job #1277209) | Cod sursa (job #1920872) | Cod sursa (job #2175046)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e6 + 5;
char a[MAXN + 1], b[MAXN + 1];
int pi[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 k = 0;
for(i = 2; i <= sza; i++) {
while(k > 0 && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
k++;
pi[i] = k;
}
k = 0;
int cnt = 0;
for(i = 1; i <= szb; i++) {
while(k > 0 && a[k + 1] != b[i])
k = pi[k];
if(a[k + 1] == b[i])
k++;
if(k == sza) {
cnt++;
if(cnt <= 1000) {
sol.push_back(i - sza);
}
}
}
fprintf(fout,"%d\n" ,cnt);
for(auto it : sol) {
fprintf(fout,"%d " ,it);
}
fclose(fi);
fclose(fout);
return 0;
}