Simple mode matching and improvement pattern matching (KMP) algorithm illustrated Lewislau Preface: Recent review of data structure, before the teacher said, it is ignored. Khan, our school's indeed cattle B. Some brothers told me that KMP is basically a more difficult algorithm in the data structure, so it has mastered it, at least psychologically give me a lot of encouragement, but this algorithm is that I asked the teacher to master, huh. The speech is transmitted, and the KMP algorithm begins. In the case of the improved pattern match (KMP) algorithm, we will first say simple mode match: It is actually very simple, it is two string bitmap comparisons. In mode match: We assume that the string P looks up in the string t. At this point, P is called a pattern string, called T is a target string. OK, I generally prefer to explain the problem with instances. T: A B D A B D A B C P: A B D A B
Simple pattern matching algorithm
The simple model matching algorithm is to compare with P and T, that is, the first comparison: T: A B D A B D A B C P: A B D A B C Discovered the sixth element (5 5 ) D and C are not equal, the first one ends, at this time, 6 times (6 elements) are compared. Second comparison: T: A B D A B D A B C P: A B D A B C The first element is not equal, the second is over, and it compares 1 time (1 element) at this time. Third, comparison: T: A B D A B D A B C P: A B D A B C The first element is not equal, the third is over, and it compares 1 time (1 element) at this time. The fourth comparison: T: A B D A B D A B C P: A B D A B C The first element is equal, the second element is also equal, the third, four, five, six, equal, match success At the end of the fourth, six times (6 elements) were compared. Matching success, a total of 14 times. But this is the matching scheme under our ideal, and the length of the string is far more than this. This algorithm is an algorithm that has been reversed, becoming a simple pattern matching algorithm. Suppose: The length of the target T is N, the mode P length is m, then in the worst case, the number of times can be reached: (n - m 1) * M times; in numerous occasions, M is far less than n, it The time complexity is O (n * m).
Improved pattern matching (KMP) algorithm
