Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:请教这题用KMP方法的思路In Reply To:请教这题用KMP方法的思路 Posted by:orangeman at 2009-09-18 02:38:33 > many thanks. 我不懂怎么表达,但可以参考下 这个算法利用next数组的意义:next[i] == j 代表 str[1..j] == str[i - j + 1, i] (这里字符串下标从1开始) 设有n个字符串str1,str2,...,strn 先取第一个字符串str1为 比较字符串 然后对str2,...,strn都执行以下操作: 枚举str1的所有后缀 和 stri (2<= i <= n)合并成 新的字符串str, 然后求str的next 根据next的值就可以知道最长连续公共子字符串长度 这里我不知道怎么表达,还是根据题目样例自己分析,大概就是这样一个方程 最长连续公共子字符串的长度 = max{min{max{...}}}。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator