Cod sursa(job #1090502)

Utilizator kiralalaChitoraga Dumitru kiralala Data 22 ianuarie 2014 19:20:03
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
#define P 10007
//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 subKey;
int subLen;
int powConst=1;
int key;
queue<int> output;

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

    return r;
}

int NextKey(int key, char A, char B)
{
    int a=A-'A',b=B-'A';

    return ((key-(a*powConst)%P+P)*26+b)%P;
}

int IsGood(int i)
{
    for(int j=0;j<subLen;++j)
        if(str[i+j]!=substr[j])
            return 0;
    return 1;
}

int main()
{
    scanf("%s\n%s",substr,str);
    subLen=strlen(substr);
    int strLen=strlen(str);
    if(subLen>strLen) printf("0");
    else {
    subKey=Hash(substr,0,subLen);
    key=Hash(str,0,subLen);
    int n=0;
    for(int i=0;i<strLen-subLen+1&&n<1000;i++)
    {
        if(key==subKey)
            if(IsGood(i))
            {
                n+=1;
                output.push(i);
            }
        key=NextKey(key,str[i],str[i+subLen]);
    }
    printf("%d\n",n);
    while(!output.empty())
    {
        printf("%d ",output.front());
        output.pop();
    }
    }
    return 0;
}