Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <fstream>
- #include<stdio.h>
- #include<string.h>
- #define NO_OF_CHARS 256
- using namespace std;
- void naive_search(string pat, string txt)
- {
- int M = pat.length();
- int N = txt.length();
- /* A loop to slide pat[] one by one */
- for (int i = 0; i <= N - M; i++)
- {
- int j;
- /* For current index i, check for pattern match */
- for (j = 0; j < M; j++)
- {
- if (txt[i + j] != pat[j])
- break;
- }
- if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
- {
- printf("Pattern found at index %d n", i);
- }
- }
- }
- int goNextState(string pattern, int num_total_state, int state, int given_character) {
- // If our character match with the pattern
- if (state < num_total_state && given_character == pattern[state])
- return state + 1;
- int nextstate, index;
- //If dont match, search the maximum legth of matched pattern
- // For example pattern is = aabb and our index is aabc , start to match first character of pattern and last character of given index increasingly and decreasingly..
- for (nextstate = state; nextstate > 0; nextstate--)
- {
- if (pattern[nextstate - 1] == given_character) // start to find longest matched substring
- {
- for (index = 0; index < nextstate - 1; index++) {
- if (pattern[index] != pattern[state - nextstate + 1 + index])
- break;
- }
- if (index == nextstate - 1)
- return nextstate;
- }
- }
- return 0;
- }
- void Transition_Table(string pattern, int lengt_of_pattern, int Table_Array[][NO_OF_CHARS])
- {
- int given_character;
- int state;
- for (state = 0; state <= lengt_of_pattern; state++)
- for (given_character = 0; given_character<NO_OF_CHARS; ++given_character)
- Table_Array[state][given_character] = goNextState(pattern, lengt_of_pattern, state, given_character);
- }
- void Automata_Compute(string pattern, string given_text) {
- int numberOfLine = 0;
- int count = 0;
- int A = pattern.length();
- int B = given_text.length();
- int Table_Array[50][NO_OF_CHARS];
- Transition_Table(pattern, A, Table_Array);
- int i, state = 0;
- for (i = 0; i<B; i++) {
- // get input ...
- istringstream stream(given_text);
- string line;
- for (int a = 0; getline(stream, line); ++a) {
- state = Table_Array[state][given_text[i]];
- if (state == A) {
- count++;
- printf("n pattern found at line %d , %d", a, count);
- }
- }
- }
- }
- // Driver program to test above function
- int main()
- {
- /*ifstream file("stringExample");
- string content((istreambuf_iterator<char>(file)),
- (istreambuf_iterator<char>()));*/
- ifstream ifile("stringExample.txt"); // open
- string str(istreambuf_iterator<char>(ifile), {});
- string pat = ("AABA");
- string text = (str);
- naive_search(pat, text);
- Automata_Compute(pat, text);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement