Cod sursa(job #1198155)

Utilizator MaarcellKurt Godel Maarcell Data 14 iunie 2014 19:05:14
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define prim 73
#define mod1 666013
char A[2000005],B[2000005]; int l1,l2,k;
vector<int> match;
bool check(int x){
    int k=0;
    for (int 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;
    int primp=1,i=0;
    if (l1>l2) {printf("0"); return 0; }

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

        j++;
        }



    int 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  )) * 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;

}