Pagini recente » Cod sursa (job #1045354) | Cod sursa (job #1721952) | Cod sursa (job #1845237) | Cod sursa (job #2131271) | Cod sursa (job #2235603)
#include<fstream>
#define prim1 100007
#define prim2 100021
#define baza 122
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000007], b[2000007];
int n,m, key1, key2, v1, v2, p1,p2, nr;
bool occ[2000007];
int main(){
fin>>a>>b;
n = strlen(a);
m = strlen(b);
if(n>m){
fout<<0;
return 0;
}
p1 = 1; p2 = 1;
key1 = a[0]; key2 = a[0];
v1 = b[0]; v2 = b[0];
for(int i = 1; i<n; ++i){
key1 = ((key1*baza)+a[i])%prim1;
key2 = ((key2*baza)+a[i])%prim2;
v1 = ((v1*baza)+b[i])%prim1;
v2 = ((v2*baza)+b[i])%prim2;
p1 = (p1*baza)%prim1;
p2 = (p2*baza)%prim2;
}
nr = 0;
if(key1 == v1 && key2 == v2){
occ[0]=true; nr++;
}
for(int i = n; i<m; ++i){
v1 = ((v1 - (p1*b[i-n])%prim1 + prim1)*baza + b[i])%prim1;
v2 = ((v2 - (p2*b[i-n])%prim2 + prim2)*baza + b[i])%prim2;
if(v1 == key1 && v2 == key2){
nr++;
occ[i-n+1] = true;
}
}
fout<<nr<<'\n';
nr = 0;
for(int i = 0; i<m && nr<1000; ++i){
if(occ[i] == true){
nr++;
fout<<i<<' ';
}
}
return 0;
}