Pagini recente » Cod sursa (job #3212174) | Cod sursa (job #2651877) | Cod sursa (job #2060608) | Cod sursa (job #3245398) | Cod sursa (job #830553)
Cod sursa(job #830553)
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[200007];
char h[200006];
int H[200005];
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 && 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 && 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[q];
}
}
fout << nr <<'\n';
for(int i = 1; i <=min(1000, nr); i++)
fout<< ret[i] <<" ";
fin.close();
return 0;
}