Pagini recente » Cod sursa (job #1123553) | Cod sursa (job #344530) | Cod sursa (job #564976) | Autentificare | Cod sursa (job #830546)
Cod sursa(job #830546)
#include<fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[200007];
char h[200006];
int H[200005];
int ret[200007];
int nr;
void read(){
fin >> h + 1;
fin >> s + 1;
}
void solve(){
int k = 0 ;
H[1] = 0;
for(int i = 2; i <=strlen(h + 1); 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; i <= strlen(s + 1); i++){
if(q && s[i] != h[q + 1])
q = H[q];
if(s[i] == h[q + 1])
q++;
if(q == strlen(h + 1) )
ret[++nr] = i - q ;
}
fout << nr <<'\n';
for(int i = 1; i <= nr; i++)
fout<< ret[i] <<" ";
fin.close();
return 0;
}