• Post Reply Bookmark Topic Watch Topic
  • New Topic

Counting character comparisons with KMP substring search.  RSS feed

 
Kevin Garcia
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am using the KMP (Knuth-Morris-Pratt) algorithm for substring search. And I want to count the character comparisons. But I do not know where I have to do that and where to start..

See the code below: (http://algs4.cs.princeton.edu/53substring/KMP.java.html)



And to search:



I would like to have some assistance on where I can count the character comparisons.
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Loosely, it would be line 7 where a character is used as an offset into the array.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kevin Garcia wrote:I am using the KMP (Knuth-Morris-Pratt) algorithm for substring search. And I want to count the character comparisons. But I do not know where I have to do that and where to start..

I think Carey got it for you, but R seems wrong to me, unless you're only allowing ascii characters. Otherwise it would be 65536, which could make that 'dfa' sucker "!#%ing huge.

BTW, I don't see ANY reference, either in your code or Princeton's, as to what 'dfa' means - beyond the fact that 'a' probably stands for "automaton" - which makes it a bad name.

And if this isn't just a class exercise, I find Boyer-Moore-Horspool waaay simpler than KMP; and it's MUCH more compact.

Winston
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
DFA = Deterministic Finite Automaton
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!