• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Devaka Cooray
  • Ron McLeod
  • paul wheaton
Saloon Keepers:
  • Tim Moores
  • Piet Souris
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Frits Walraven
  • Scott Selikoff

Counting character comparisons with KMP substring search.

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Saloon Keeper
Posts: 9707
79
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Loosely, it would be line 7 where a character is used as an offset into the array.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 9707
79
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
DFA = Deterministic Finite Automaton
 
I just had the craziest dream. This tiny ad was in it.
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic