Pagini recente » Cod sursa (job #3233647) | Cod sursa (job #2459160) | Cod sursa (job #3235308) | Cod sursa (job #2591802) | Cod sursa (job #629457)
Cod sursa(job #629457)
#include <fstream>
#define BAZA 67
#define LMAX 2000000
#define P 1000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,nr1,nr2,b[LMAX],poz[LMAX],sol;
void puteri(int l){
int i;
b[0]=1;
for(i=1;i<=l;i++)
b[i]=(b[i-1]*BAZA)%P;
}
void read(){
ifstream f("strmatch.in");
f>>B>>A;
m=strlen(A);
n=strlen(B);
puteri(n);
}
int hash(char v[LMAX],int l)
{
int i,nr=0;
for(i=0;i<l;i++){
if(v[i]>='a' && v[i]<='z')
nr=nr+b[l-i-1]*(v[i]-'a'+1)%P;
if(v[i]>='A' && v[i]<='Z')
nr=nr+b[l-i-1]*(v[i]-'A'+27)%P;
if(v[i]>='0' && v[i]<='9')
nr=nr+b[l-i]*(v[i]-'0'+53)%P;
}
return nr;
}
void solve(){
int i;
nr1=hash(B,n);
nr2=hash(A,n);
if(nr1==nr2) poz[++sol]=0;
for(i=0;i<m-n;i++){
if(A[i]>='a' && A[i]<='z')
nr2=nr2-b[n-1]*(A[i]-'a'+1)%P;
if(A[i]>='A' && A[i]<='Z')
nr2=nr2-b[n-1]*(A[i]-'A'+27)%P;
if(A[i]>='0' && A[i]<='9')
nr2=nr2-b[n-1]*(A[i]-'0'+53)%P;
nr2=nr2*BAZA%P;
if(A[i+n]>='a' && A[i+n]<='z')
nr2=nr2+A[i+n]-'a'+1;
if(A[i+n]>='A' && A[i+n]<='Z')
nr2=nr2+A[i+n]-'A'+27;
if(A[i+n]>='0' && A[i+n]<='9')
nr2=nr2+A[i+n]-'0'+53;
if(nr1==nr2) poz[++sol]=i+1;
}
}
void write(){
int i;
ofstream g("strmatch.out");
g<<sol<<"\n";
for(i=1;i<=sol;i++)
g<<poz[i]<<" ";
}
int main(){
read();
solve();
write();
return 0;
}