Heisenberg302's blog

By Heisenberg302, history, 8 years ago, In English

Hey, I have a question regarding Kmp. lets say I have a string s1 and a string s2. I want to know if s2 is in s1 or not. for this goal, can I add the second string s2 to the beginning of s1 and run preKmp algorithm , the code would look something like this :

        int n=toBeFound.size()+s.size(); //s is string in which toBeFound will be searched
	int i = 0 ; 
	int j= -1;
	s=toBeFound+s;
	int best =0;
	F[0]=-1;
	while (i < n) {
		while ( j>=0 && s[i] != s[j]) j = F[j];
		i++;
		j++;
		F[i] = j;
		if(j==toBeFound.size()){
			cout<<i-j-j<<endl; //starting index
			cout<<s.substr(i-j,j); //the found word
			break;
		}
	}

Edit: there should be some more conditions while checking the found string.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by Heisenberg302 (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Yes, this is basicly how its done for finding T in S:

U create new string .. let it be TT = T + '#'(actually any symbol thats not in T neither in S) + S and run kmp for this TT string.

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank you that makes sense. Also I dont understand some people. Why would you even give a down vote for this post ? I am basically trying to learn something, please just leave the blog if you dont want to teach something.