Cod sursa(job #768315)

Utilizator mi5humihai draghici mi5hu Data 16 iulie 2012 16:36:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <stdio.h>
#include <string>
#include <fstream>
#define MOD 1000000001
#define BASE 131
#define easyT 1
#define RollT 2

using namespace std;

string Str, subStr;
int sL, subL;
long long hashSubS, hashS;
int nr, Sol[1001];
int T;

void read_() {
     ifstream fin("strmatch.in");
     fin >> subStr;
     fin >> Str;  
     sL = Str.length(); 
     subL = subStr.length();  
     fin.close();
}

void search(int i) {
     if (hashSubS == hashS) {
         if (nr < 1000) {
             Sol[nr] = i - subL + 1;               
         }
         nr++;   
     }     
}

void searchEasy(int i) {
     if (hashSubS == hashS) {
         if (Str.compare(i - subL + 1, subL, subStr) == 0) {
             if (nr < 1000) {
                 Sol[nr] = i - subL + 1;               
             }
             nr++;   
         }
     }     
}

void get_Easy_Hash() {
     int S = 0;
     
     for (int i = 0; i < subL; i++) {   
         hashS += Str[i];
         hashSubS += subStr[i];
     }
     
     search(subL - 1);
     for (int i = subL; i < sL; i++) {
         hashS = hashS + Str[i] - Str[i - subL];
         searchEasy(i);
     }
}

void get_Rolling_Hash() {        
     long long pw = 1; 
     for (int i = 0; i < subL; i++) {  
         hashS = (hashS * BASE + Str[i]) % MOD;           
         hashSubS = (hashSubS * BASE + subStr[i]) % MOD;
         if (subL < sL * 7 / 9) {
             pw = (pw * BASE) % MOD;
         } 
     }     
     search(subL - 1);     
     
     for (int i = subL; i < sL; i++) {
         hashS = ((hashS * BASE + Str[i])  - (pw * Str[i - subL])) % MOD;
         if (hashS < 0) {
             hashS += MOD;            
         }
         search(i);
     }       
}

void printSol() {
     printf("%d\n", nr);
     if (nr > 1000) {
         nr = 1000;   
     }
     for (int i = 0; i < nr; i++) {
         printf("%d ", Sol[i]);
     }          
}

int getType() {
     if  (subL < sL * 7 / 9) {
         return RollT;
     }
     return easyT;   
}

int main(){
    freopen("strmatch.out", "w", stdout);
    read_();  
    
    T = getType();
    if (T == RollT) {
        // Are rost sa folosesc o fct de hash mai complexa
        get_Rolling_Hash();
    } else {
        // Pierd prea mult timp cu fuctia de hash => folosesc una mai simpla.
        get_Easy_Hash();
    }    
    printSol();
            
    return 0;
}