Cod sursa(job #751768)

Utilizator memaxMaxim Smith memax Data 26 mai 2012 20:58:13
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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;  
    for(int i=0; i<m-1; i++){
            z=z*63+go(B[i]); z%=q;
            y=y*63+go(A[i]); y%=q;
            h*=63;
            h%=q;
            }
    queue<int> Q;
    z=z*63+go(B[m-1]); z%=q;
    y=y*63+go(A[m-1]); y%=q;
    bool t;
    for(int i=m; i<=n; i++){
            if(z==y){
                     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); }
                     }
            if(Q.size()>999){ break; }
            y=(63*((y-go(A[i-m])*h)%q+q)+go(A[i]))%q;
            }
    cour << Q.size() << "\n";
    while(!Q.empty()){
                      cour << Q.front() << " ";
                      Q.pop();
                      }
    return 0;
    }