Pagini recente » Cod sursa (job #3279974) | Cod sursa (job #751230) | Cod sursa (job #2840248) | Cod sursa (job #3261696) | Cod sursa (job #629580)
Cod sursa(job #629580)
#include <fstream>
#include <cstring>
#define BAZA 67
#define LMAX 2000011
#define P 1000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,poz[LMAX],sol,b[LMAX],nr1,nr2;
void puteri(int l){
int i;
b[0]=1;
for(i=1;i<=l;i++)
b[i]=(b[i-1]*BAZA)%P;
}
inline int numar(char c)
{
if(c>='a'&&c<='z') return (c-'a'+1);
if(c>='A'&&c<='Z') return (c-'A'+27);
return (c-'0'+53);
}
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++)
nr=(nr+b[l-i-1]*numar(v[i])%P)%P;
return nr;
}
void solve(){
int i,j,ok;
nr1=hash(B,n);
nr2=hash(A,n);
if(nr1==nr2) {
/*ok=1;
for(i=0;i<n;i++)
if(A[i]!=B[i]) ok=0;
if(ok) */ poz[++sol]=0;
}
for(i=0;i<m-n;i++){
nr2=(P+nr2-(b[n-1]*numar(A[i]))%P)%P;
nr2=(nr2*BAZA)%P;
nr2=(nr2+numar(A[i+n]))%P;
if(nr1==nr2) {
/*ok=1;
for(j=0;j<n;j++)
if(A[i+j+1]!=B[j]) ok=0;
if(ok)*/ poz[++sol]=i+1;
}
}
}
void write(){
int i;
ofstream g("strmatch.out");
g<<sol<<"\n";
for(i=1;i<=sol && i<=1000;i++)
g<<poz[i]<<" ";
}
int main(){
read();
solve();
write();
return 0;
}