E D R S I H C RSS
ID
Password
Join
You can do very well in speculation where land or anything to do with earth is concerned.

FrontPage Boyer-Moor

#include <iostream>
#include <fstream>
#include <string>
using namespace std;


class Solution {
public:
    Solution();
    ~Solution();
    void solve(const char *input, const char *output);

private:
    fstream source_fp;
    fstream target_fp;
};


int main() {
    Solution solve;

    solve.solve("input_bm.txt", "output.txt");

    return 0;
}


Solution::Solution() {

}

Solution::~Solution() {
    source_fp.close();
    target_fp.close();
}



void Solution::solve(const char *input,const char *output) {
    int nCount = 0;
    int i = 0, j = 0, idx = 0, k = 0;
    int alphabet[26] = { 0, };
        
    source_fp.open(input,ios::in);
    target_fp.open(output,ios::out);
   
    source_fp >> nCount;
    
    for ( idx = 0; idx < nCount; idx++ ) {
       string pi;
       string text;
       
       source_fp >> pi;
       int pi_length = pi.size();
       
       for ( j = 0; j < 26; j++ ) {
           alphabet[j]  = pi_length;	       
       }
         
       for ( j = 0; j < pi_length-1; j++) {
           alphabet[ pi[j] - 'a' ] = pi_length - j - 1;
       }
      
       source_fp >> text;
       int text_length = text.size();
       int fin = text_length - pi_length + 1;
       
       for (i = 0; i < fin; ) {
       	       j = pi_length-1;
       	       k = i + pi_length - 1; 
       	       while ( j >= 0 && pi[j] == text[k] ) {
       	       	       j--;
       	       	       k--;
       	       }
       	       if ( j == -1 ) {
       	       	       cout << "Found : " << i+1 << endl;
       	       	       break;
       	       } else {
       	           i += alphabet[ text[i+pi_length-1] - 'a' ];      
       	       }
       	       	     
       }
    }
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2013-06-04 00:33:59
Processing time 0.4564 sec