Cod sursa(job #1198157)

Utilizator MaarcellKurt Godel Maarcell Data 14 iunie 2014 19:13:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define prim 73
#define mod1 666013
#define int64 long long
char A[2000005],B[2000005]; int64 l1,l2,k;
vector<int64> match;
bool check(int64 x){
    int64 k=0;
    for (int64 i=x-l1+1; i<=x; i++)
        if (A[k++]!=B[i]) return false;
    return true;


}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s", &A, &B);

    l1 = strlen(A);
    l2 = strlen(B);
    k=0;
    int64 primp=1,i=0;
    if (l1>l2) {printf("0"); return 0; }

    int64 j =0;  int64 hashB=0;
    while (j<l1){
        hashB=(hashB*prim + B[j]) % mod1;

        j++;
        }



    int64 hashA=0;
    for (i=0; i<l1; i++){
        hashA=(hashA*prim + A[i]) % mod1;
        if (i!=0){primp=(primp*prim) % mod1;}


    }




    if (hashA==hashB) if (check(l1-1))  {k++; match.push_back(0);}
    for (i=l1; i<l2; i++){

        hashB=((hashB-((B[i-l1]*primp)% mod1 ) + mod1) * prim +B[i]) % mod1;

        if (hashA==hashB) if (check(i)) {k++; match.push_back(i-l1+1);}
    }
    printf("%d\n",k);
    for (i=0; i<k; i++)
        printf("%d ",match[i]);
    return 0;

}