※ 引述《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