#include <iostream>

using namespace std;

class KarpRabin
{
private:
    string text;
    string pattern;
    int textSize;
    int patternSize;

    int Hash(const string t);
    int Rehash(int preHash, int coefficient, int start);
    bool subCheck(int i){
        for (int j = 0; j < patternSize; j++)
            if (text[i + j] != pattern[j])
                return false;
        return true;
    }
public:
    KarpRabin(){}
    KarpRabin(string t){ text = t; patternSize = 0; textSize = t.length(); }
    void Search_Text(string p);
};
int KarpRabin::Hash(const string t)
{
    int i = 0,j=0;
    int hash = 0;
    if (t.length() < patternSize)
        return -1;

    for (i = (patternSize - 1),j=0; i >= 0; i--,j++){
        hash += (t[j]) * (int)(0x01<<i);
    }
    return hash;
}
int KarpRabin::Rehash( int preHash, int coefficient,int start)
{
    return ((preHash - (text[start-1] * coefficient)) * 2) + text[start + patternSize-1];

}
void KarpRabin::Search_Text(string p)
{
    int i = 0;
    int coeff = 1;
    int textHash = 0;
    int patternHash = 0;
    pattern = p;
    patternSize = pattern.length();
    coeff <<= patternSize - 1;

    patternHash = Hash(pattern);
    textHash = Hash(text);

    for (i = 1; i <= textSize - patternSize; i++){
        if (patternHash == textHash)
            if (subCheck(i-1))
                cout << i-1 << " : " << pattern.c_str() << endl;
        textHash = Rehash(textHash, coeff,i);
    }
}


////////////////////////////////////// 메인

#include <iostream>
#include "graph.h"
#include "strinfSearch.h"
#define TXT_BUFFER 512

using namespace std;


int main(int argc,char** argv)
{
    char* FilePath;
    string pattern;
    string text;
    FILE* fp;
    char buf[TXT_BUFFER];
    KarpRabin* k;

    if (argc < 3){
        FilePath = "input.txt";
        pattern = "How";
    }
    else{
        FilePath = argv[1];
        pattern = argv[2];
    }

    if ((fopen_s(&fp,FilePath, "r")) != 0){
        cout << "fail open file" << endl;
        return 1;
    }

    while (fgets(buf, TXT_BUFFER, fp) != NULL){
        text.append(buf);
    }
    fclose(fp);

    k = new KarpRabin(text);
    k->Search_Text(pattern);

    return 0;
}