Cod sursa(job #1090566)

Utilizator kiralalaChitoraga Dumitru kiralala Data 22 ianuarie 2014 20:06:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
#define P1 100007
#define P2 1000013
//CU RABIN KARP
using namespace std;

FILE* f=freopen("strmatch.in","r",stdin);
FILE* o=freopen("strmatch.out","w",stdout);

char str[NMAX],substr[NMAX];
int subKey1,subKey2;
int subLen;
int powConst1=1,powConst2=1;
int key1,key2;
queue<int> output;

int Hash(char st[], int pa, int pb, int k, int &powConst)
{
    int r=0;
    int pow=1;
    for(int i=pb-1;i>=pa;--i)
    {
        char x=st[i];
        r=(r+x*pow)%k;
        powConst=pow;
        pow=(pow*128)%k;
    }

    return r;
}

int main()
{
    scanf("%s\n%s",substr,str);
    subLen=strlen(substr);
    int strLen=strlen(str);
    if(subLen>strLen) printf("0");
    else {
    subKey1=Hash(substr,0,subLen,P1,powConst1);
    key1=Hash(str,0,subLen,P1,powConst1);
    subKey2=Hash(substr,0,subLen,P2,powConst2);
    key2=Hash(str,0,subLen,P2,powConst2);
    int n=0;
    for(int i=0;i<strLen-subLen+1;i++)
    {
        if(key1==subKey1&&key2==subKey2) {
                n+=1;
                if(n<=1000)
                output.push(i);
        }
        key1=((key1-(str[i]*powConst1)%P1+P1)*128+str[i+subLen])%P1;
        key2=((key2-(str[i]*powConst2)%P2+P2)*128+str[i+subLen])%P2;
    }
    printf("%d\n",n);
    while(!output.empty())
    {
        printf("%d ",output.front());
        output.pop();
    }
    }
    return 0;
}