Pagini recente » Cod sursa (job #3278688) | Cod sursa (job #751234) | Cod sursa (job #3299905) | Cod sursa (job #3248017) | Cod sursa (job #629607)
Cod sursa(job #629607)
#include <fstream>
#include <cstring>
#define BAZA 67
#define LMAX 2000011
#define P 1000007
#define Q 2000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,poz[1000],sol,p1[LMAX],p2[LMAX],a1,b1,a2,b2;
void puteri(int l){
int i;
p1[0]=1;
p2[0]=1;
for(i=1;i<=l;i++){
p1[i]=(p1[i-1]*BAZA)%P;
p2[i]=(p2[i-1]*BAZA)%Q;
}
}
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);
}
void hash(char v[LMAX],int l, int &nr1, int &nr2)
{
int i;
nr1=0; nr2=0;
for(i=0;i<l;i++){
nr1=(nr1+p1[l-i-1]*numar(v[i])%P)%P;
nr2=(nr2+p2[l-i-1]*numar(v[i])%Q)%Q;
}
}
void solve(){
int i;
hash(B,n,a1,a2);
hash(A,n,b1,b2);
if(a1==b1 && a2==b2)
poz[++sol]=0;
for(i=0;i<m-n;i++){
b1=(P+b1-(p1[n-1]*numar(A[i]))%P)%P;
b1=(b1*BAZA)%P;
b1=(b1+numar(A[i+n]))%P;
b2=(Q+b2-(p2[n-1]*numar(A[i]))%Q)%Q;
b2=(b2*BAZA)%Q;
b2=(b2+numar(A[i+n]))%Q;
if(a1==b1 && a2==b2)
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;
}