string - Confused regarding pre-processed table in KMP -

-

Looking at the KMP algorithm, and confused about a specific row in KMP that calculates the suffix-prefix table of the numbers.

algorithm kmp_table: input: an array of characters, W (words to be analyzed) an array of integers, T (table) To fill) Output: Nothing (but it shows the table during operation) 
  Define the variable: An integer, position 2 (In the current situation, we do computing in t Are) an integer, CNG ??? 0 (Zero-based index in the W of the next character of the current candidate sub-group) (First few values ​​have been set but different from the suggestion from the algorithm) T [0] One ???? -1, t [1] a ???? 0 When the position is less than the length of W, we do: (first case: the object is turned on) W [pause -1] = w [cnd], cd c cnd + 1, t [pause] a ???? CNG, POS one ???? Position + 1 (second case: this is not, but we can come back) Otherwise, if CD & gt; 0, CDAD Do T [Cnd] (Third Case: We have run away from the candidates. Note CND = 0) Otherwise, T [Pause] 0, Position POS + 1   
 above from Wikipedia Straight away I'm a bit confused if  cnd> 0  why  cnd: = T [cnd] , should not reset it back to 0, as if we are starting again?  
 
 
 
 Obviously,  T [0] = -1  and therefore  Cnd  to set  t [cnd = 0] = -1  next to iterations  w [cnd = -1]  will be read and the string Is outside For at least this reason, you need a special treatment for  cnd> 0  vs  cnd == 0 .  
 For the actual reason we compare 0 from  cnd  is that  T [cnd]  us  w []  Should be given to the location where there is a partial string match on the left of  w [cnd] .  T [0] , however, can not be used for this purpose because there is nothing on the left side of  w [0] .  
 
 Why to set the CD: = T [Cnd], should not reset the CDD back to 0, as if we are starting again?   
 If you restart the position 0 after partial matching, you return to the nive algorithm. There is a rewind status in  T [] , as you can see from the sample tables with  w []  and  T []  Not always right below 0. So, instead of going back to the position of 0, you sometimes go to other positions and keep on matching with it. And this is what makes the algorithm more scalable.

Comments

Post a Comment

Popular posts from this blog

excel vba - How to delete Solver(SOLVER.XLAM) code -

-
After opening several examples of macro / code written, I suddenly get stuck with a code that seems safe. Solver (SOLVER.XLAM) is doing this notation and I would like to remove it from my system. I do not think this is a relativant code. Can anyone tell me what should I do? I have already installed something to remove the password but Solver is still asking for password and I can not get rid of it! itemprop = "text"> Solver Excel is add-in If you want to delete it, then Excel Application & gt; Options & gt; Add-ins & gt; Search for 'Go to' button and gt; Uncheck the solver on the list like press something (I can not give you the exact path because I have the Polish version of Excel). Trying to open Solver's VBA code is not good because it There is allegedly copyright. Besides, I do not think Solver creates any disadvantages while working with Excel or VBA.
Read more

github - Teamcity & Git - PR merge builds - anyway to get HEAD commit hash? -

-
I have a team city build project with Gitbab VCS route, I have been triggered for both / head on PR and / Merge the referee. The annoying thing is that you can not do anything useful with the merged hash - it is not present in Gitobb. I want to exclude newsgate packages with head in gutub comet situations in the version number along with Hewash (Newsaging 7) for the music build, but against head hash. However, I can not see a way to get the head hashes while constructing that merge. I just want to head because it's useless - we only care about merge. (PR - Pull Request) This command works reliably while running One on / merge is git log --no-merge -1 ---- = '% h'
Read more

ios - Replace text in UITextView run slowly -

-
I have a UITextView and I change a word like the code at the end of UITextView.text: - (void) Replace TexttechWitWord: (NSString *) word {NSString * currentTextViewText = self.textView.text; CurrentTextViewText = [currentTextViewText stringByReplacingCharactersInRange: NSMakeRange ([self.textView.text length] - [word length], [word length]) withString: word; Self.textView.text = currentTextViewText; } Replacement work is fine, but it runs very slowly and very slowly when the textView now lengthens Is there any better way? I try the replacement range: with text for a week but still stuck. Not to know how to use it to replace it in your case. Please guide! Thanks in advance! This is an important job. As you are using an irreversible string and you are creating a very long string and before Assigned to NSString created from. NSString will be used instead of NSMutableString . - (UITableViewCell *) TableView: (UITableView *) Table View CellForOutPath: (NSIndex...
Read more