Pagini recente » Cod sursa (job #2379584) | Cod sursa (job #1660822) | Cod sursa (job #590539) | Cod sursa (job #329457) | Cod sursa (job #570790)
Cod sursa(job #570790)
#include<cstdio>
#include<cstring>
#include<vector>
#define Lmax 2000010
#define theymatch hashB1 == hashA1 && hashB2 == hashA2
#define P 73
#define M1 100007
#define M2 100021
using namespace std;
int lung_a,lung_b,hashA1,hashA2,hashB1,hashB2,P1,P2;
vector <int> sol;
char a[Lmax],b[Lmax];
bool isletter(const char &x){
if(x>='A' && x<='Z')
return 1;
return 0;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,Lmax,stdin);
fgets(b,Lmax,stdin);
if(!isletter(a[strlen(a)-1]))
a[strlen(a)-1]='\0';
if(!isletter(b[strlen(b)-1]))
b[strlen(b)-1]='\0';
lung_a=strlen(a);
lung_b=strlen(b);
P1=P2=1;
hashA1 = hashA2 = 0;
for(int i=0 ; i<lung_a; ++i){
hashA1 = (hashA1 * P + a[i] ) % M1;
hashA2 = (hashA2 * P + a[i] ) % M2;
if(i!=0){
P1 = (P1 * P) %M1;
P2 = (P2 * P) %M2;
}
}
if( lung_b < lung_a)
{ printf("0");
return 0;
}
hashB1 = hashB2 = 0;
for(int i=0 ; i<lung_a; ++i)
hashB1 = (hashB1 * P + b[i] ) % M1,
hashB2 = (hashB2 * P + b[i] ) % M2;
if(theymatch)
sol.push_back(0);
for(int i=lung_a; i<lung_b;++i ){
// hasul curent = cel anterior minus prima litera + litera curenta
hashB1 = ((hashB1 - (b[i-lung_a] * P1) %M1 + M1) * P + b[i]) %M1;
hashB2 = ((hashB2 - (b[i-lung_a] * P2) %M2 + M2) * P + b[i]) %M2;
if(theymatch)
sol.push_back(i-lung_a+1);
}
printf("%d\n",sol.size());
for(vector<int>::iterator it=sol.begin();it!=sol.end();++it)
printf("%d ",*it);
return 0;
}