Cod sursa(job #752844)

Utilizator memaxMaxim Smith memax Data 29 mai 2012 18:36:22
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

int go(char a){
    int u=int(a);
    if(u<91 && u>64){ return(u-64); }
    if(u>96 && u<123){ return(u-70); }
    if(u<58){ return(u+5); }
    }

int main(){
    ifstream cinr ("strmatch.in");
    ofstream cour ("strmatch.out");
    string A, B;
    cinr >> B;
    cinr >> A;
    int n=A.size(), m=B.size();   
    int r,q=100007,h=1,z=0,y=0,z1=0,y1=0,q1=100013,ch,ch1,h1=1;  
    for(int i=0; i<m-1; i++){
            ch=go(B[i]);
            z=z*63+ch; z%=q;
            z1=z1*63+ch; z1%=q1;
            ch=go(A[i]);
            y=y*63+ch; y%=q;
            y1=y1*63+ch; y1%=q1;
            h*=63;
            h%=q;
            h1*=63;
            h1%=q1;
            }
    queue<int> Q;
    z=z*63+go(B[m-1]); z%=q;
    y=y*63+go(A[m-1]); y%=q;
    z1=z1*63+go(B[m-1]); z1%=q1;
    y1=y1*63+go(A[m-1]); y1%=q1;
    bool t;
    for(int i=m; i<=n; i++){
            if(z==y && z1==y1){
                     t=true;
                     for(int j=0; j<m; j++){
                             if(A[j+i-m]!=B[j]){ t=false; break; }
                             } 
                     if(t){ Q.push(i-m); }
                     }
            ch=go(A[i]);
            ch1=go(A[i-m]);
            y=(63*((y-ch1*h)%q+q)+ch)%q;
            y1=(63*((y1-ch1*h1)%q1+q1)+ch)%q1;
            }
    cour << Q.size() << "\n";
    int tr=1;
    while(!Q.empty() && tr<=1000){
                      cour << Q.front() << " ";
                      Q.pop();
                      tr++;
                      }
    return 0;
    }