Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:请教这题用KMP方法的思路

Posted by caiweiwenjs at 2012-02-21 21:52:01 on Problem 3450
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator