Pagini recente » Cod sursa (job #2837031) | Cod sursa (job #417714) | Cod sursa (job #2443513) | Cod sursa (job #783776) | Cod sursa (job #837077)
Cod sursa(job #837077)
#include<fstream>
#include<string.h>
#define nmax 2000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N;
char s[nmax], p[nmax];
int H[nmax], ret[1005];
int nr;
void read(){
fin >> p + 1;
N = strlen(p + 1);
fin >> s + 1;
}
void prelucrare(){
int q = 0;
for(int i = 2; p[i] ; i++){
while(q > 0 && p[i] != p[q + 1])
q = H[q];
if(p[i] == p[q + 1])
q++;
H[i] = q;
}
}
void solve(){
int q = 0;
for(int i = 1; s[i]; i++){
while(q && s[i] != p[q + 1])
q = H[q];
if(s[i] == p[q + 1])
q++;
if(q == N){
nr++;
if(nr <= 1000)
ret[nr] = i - q;
q = H[N];
}
}
fout << nr<<'\n';
for(int i = 1; i <= min(nr,1000); i++)
fout << ret[i] <<" " ;
}
int main()
{
read();
prelucrare();
solve();
fin.close();
return 0;
}