Cod sursa(job #768146)

Utilizator mi5humihai draghici mi5hu Data 16 iulie 2012 10:01:04
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <string>
#include <fstream>

using namespace std;

string Str, subStr;
int sL, subL;
int hash[2000000], hashS;
int nr, Sol[2000000];

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

void search() {
     for (int i = subL - 1; i < sL; i++) {
         if (hash[i] == hashS) {
             if (Str.compare(i - subL + 1, subL, subStr) == 0) {
                 Sol[nr++] = i - subL + 1;               
             }            
         }
     }     
}

void printHash(){
     for (int i = 0; i < sL; i++) {
         printf("%c %d; ", Str[i], hash[i]);
     }
     printf("\n%d\n\n", hashS);     
}

void get_hash() {          
     int S = 0;
     
     for (int i = 0; i < subL; i++) {         
         S += Str[i];
         hash[i] += S;
         hashS += subStr[i];
     }
     for (int i = subL; i < sL; i++) {
         hash[i] = hash[i-1] + Str[i] - Str[i - subL];
     }        
     //printHash();
}

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

int main(){
    freopen("strmatch.out", "w", stdout);
    
    read_();
    get_hash();
    search();    
    printSol();
    
    return 0;
}