Pagini recente » Cod sursa (job #2840123) | Cod sursa (job #2727072) | Cod sursa (job #459873) | Cod sursa (job #2892520) | Cod sursa (job #629494)
Cod sursa(job #629494)
#include <fstream>
#include <cstring>
#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;
}
inline int numar(char c){
int nr;
switch(c){
case 'a': nr=1;break;
case 'b': nr=2;break;
case 'c': nr=3;break;
case 'd': nr=4;break;
case 'e': nr=5;break;
case 'f': nr=6;break;
case 'g': nr=7;break;
case 'h': nr=8;break;
case 'i': nr=9;break;
case 'j': nr=10;break;
case 'k': nr=11;break;
case 'l': nr=12;break;
case 'm': nr=13;break;
case 'n': nr=14;break;
case 'o': nr=15;break;
case 'p': nr=16;break;
case 'q': nr=17;break;
case 'r': nr=18;break;
case 's': nr=19;break;
case 't': nr=20;break;
case 'u': nr=21;break;
case 'v': nr=22;break;
case 'w': nr=23;break;
case 'x': nr=24;break;
case 'y': nr=25;break;
case 'z': nr=26;break;
case 'A': nr=27;break;
case 'B': nr=28;break;
case 'C': nr=29;break;
case 'D': nr=30;break;
case 'E': nr=31;break;
case 'F': nr=32;break;
case 'G': nr=33;break;
case 'H': nr=34;break;
case 'I': nr=35;break;
case 'J': nr=36;break;
case 'K': nr=37;break;
case 'L': nr=38;break;
case 'M': nr=39;break;
case 'N': nr=40;break;
case 'O': nr=41;break;
case 'P': nr=42;break;
case 'Q': nr=43;break;
case 'R': nr=44;break;
case 'S': nr=45;break;
case 'T': nr=46;break;
case 'U': nr=47;break;
case 'V': nr=48;break;
case 'W': nr=49;break;
case 'X': nr=50;break;
case 'Y': nr=51;break;
case 'Z': nr=52;break;
case '0': nr=53;break;
case '1': nr=54;break;
case '2': nr=55;break;
case '3': nr=56;break;
case '4': nr=57;break;
case '5': nr=58;break;
case '6': nr=59;break;
case '7': nr=60;break;
case '8': nr=61;break;
case '9': nr=62;break;
}
return nr;
}
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;
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;
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++)
g<<poz[i]<<" ";
g<<"\n";
}
int main(){
read();
solve();
write();
return 0;
}