2020-2021:teams:legal_string:王智彪:后缀数组
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/28 15:46] 王智彪 |
2020-2021:teams:legal_string:王智彪:后缀数组 [2021/07/28 15:53] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 392: | 行 392: | ||
| 6.出现或反转后出现在每个字符串中的最长子串 | 6.出现或反转后出现在每个字符串中的最长子串 | ||
| - | 我们将所有字符串和他们倒过来的字符串用没出现过的字符分割并相连。然后把除了分隔符之外的每一个位置都标记好是哪个字符串中出现的。然后显然是二分答案。先给代码。 | + | 我们将所有字符串和他们倒过来的字符串用没出现过的字符分割并相连。然后把除了分隔符之外的每一个位置都标记好是哪个字符串中出现的。然后显然是二分答案。翻转后的字符串和翻转之前的字符串都是标记同一个字符串，一起求后缀数组，这样就可以既考虑翻转又考虑没翻转的情况了。 |
| <hidden 代码> | <hidden 代码> | ||
| 行 422: | 行 422: | ||
| return cnt == n ;//别忘了有可能最后一步才凑够，这里要重新判断一下 | return cnt == n ;//别忘了有可能最后一步才凑够，这里要重新判断一下 | ||
| } | } | ||
| + | |||
| + | //main函数中 | ||
| + | for( int i = 1 ; i <= n; i ++ ) { | ||
| + | scanf( "%s" , str ) ; | ||
| + | int l = strlen( str ) ; | ||
| + | mm = min( mm , l ) ; | ||
| + | for( int j = 0 ; j < l ; j ++ ) {//顺着存 | ||
| + | r[len] = str[j] ; | ||
| + | in[len++] = i ; | ||
| + | } | ||
| + | r[len++] = 'z' + i ;//这里一定要区别开 | ||
| + | for( int j = l - 1 ; j >= 0 ; j -- ) {//倒着存 | ||
| + | r[len] = str[j] ; | ||
| + | in[len++] = i ; | ||
| + | } | ||
| + | r[len++] = 'z' + i + n ;//这里一定要区别开 | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | 剩下的oi-wiki上的题单待补，先爬去看别的了。 | ||
2020-2021/teams/legal_string/王智彪/后缀数组.1627458410.txt.gz · 最后更改: 2021/07/28 15:46 由 王智彪
