※ 引述《cocaincola (☆★)》之銘言：
: Show that the following brute-force string matching algoritm takes average
: linear time to report all occurrences of a pattern string p in a text
: string t.
: 1:Let m = length of p;n=length of t;
: 2:for i = 1 to n-m+1 do
: 3: j=1;
: 4: while j<=m and p[j]=t[i+j-1] do
: 5: j=j+1;
: 6: if j>m then
: 7: Print i ;
還真是暴力的字串搜尋演算法阿
解說一下
因為要搜尋的字串長度為m，從第一個字開始對的話只要對到文件長度的n-m+1處就可以
裡面會開始做字串比對
i指向目前文件中被抓來跟字串p比對的m個字的第一個字
j指向p字串跟拿來比對的那m個字中目前正在比對的字
然後只要j沒有大於m，然後對照的字又一樣，
就會持續把j+1直到j大於m或比對的字不一樣
這會造成一個情況就是，如果抓來比對的這m個字跟字串p完全一樣，就會把j加到大於m
於是乎就會把i值印出來，表示在第i個字找到字串p
我個人建議最好把演算法會做的事情畫出來，並配合幾個情況演練一下就知道了
不用實際去做一個文件來比對，只要設定p字串的長度m跟比m大的文件長度n
最後再來假設
1. p[j]不等於t[i+j-1]
2. p[j]等於t[i+j-1]，但不是連續m次都這樣
3. 連續m次都是p[j]等於t[i+j-1]
這樣你會更清楚這演算法怎麼做
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.92.133