Pagini recente » Cod sursa (job #932041) | Cod sursa (job #2875197) | Cod sursa (job #746437) | Cod sursa (job #576841) | Cod sursa (job #830554)
Cod sursa(job #830554)
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000007];
char h[2000006];
int H[2000005];
int ret[1008];
int nr,M;
void read(){
fin >> h + 1;
M=strlen(h + 1);
fin >> s + 1;
}
void solve(){
int k = 0 ;
H[1] = 0;
for(int i = 2; h[i]; i++){
while(k > 0 && h[i] != h[k + 1])
k = h[k];
if(h[k + 1] == h[i])
k++;
H[i] = k;
}
}
int main(){
read();
solve();
int q = 0;
for(int i = 1; s[i]; i++){
if(q > 0&& s[i] != h[q + 1])
q = H[q];
if(s[i] == h[q + 1])
q++;
if(q == M ){
if(nr <1000)
ret[++nr] = i - q ;
q = H[M];
}
}
fout << nr <<'\n';
for(int i = 1; i <=min(1000, nr); i++)
fout<< ret[i] <<" ";
fin.close();
return 0;
}