链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

Mr.Colorful recently purchased a smart bluetooth speaker. He was quite satisfied with the speaker, except that something may went wrong when the speaker responds to him.

One day, Mr.Colorful found that the speaker produced a weird sentence, but he could not remember what exactly it said.

Based on impressions, Mr.Coloful was sure that the speaker wanted to say a sentence TTT (1≤∣T∣≤2×106)(1 \le |T| \le 2\times 10^6)(1≤∣T∣≤2×106), a string consisting of only lower case letters.

He believed that the sentence he heard sounded weird because a nonempty subinterval of TTT must have been repeated immediately after its occurrence.

Formally speaking, a string WWW is said to be a weird sentence originated from TTT, if and only if there exists two integers i,ji, ji,j (1≤i≤j≤∣T∣)(1 \le i \le j \le |T|)(1≤i≤j≤∣T∣), such that W=T1…i−1+Ti…j+Ti…j+Tj+1…∣T∣W = T_{1 \dots i - 1} + T_{i \dots j} + T_{i \dots j} + T_{j + 1 \dots |T|}W=T1…i−1​+Ti…j​+Ti…j​+Tj+1…∣T∣​,

where "+" means string concatenation and Tl…rT_{l \dots r}Tl…r​ means the substring of TTT located at l…rl \dots rl…r.

Note that Ti…jT_{i \dots j}Ti…j​ denotes an empty string when i>ji > ji>j.

Mr.Colorful opened the log of his speaker. The log is also a string SSS (1≤∣S∣≤2×106)(1 \le |S| \le 2\times 10^6)(1≤∣S∣≤2×106) consisting of only lower case letters.

Given TTT, help Mr.Colorful to find the longest substring of SSS such that it is a weird sentence originated from TTT.

If there are multiple such strings, please output the string with the leftmost start position.

输入描述:

The input consists of:

    One line containing a string SSS, the log of the speaker.

    One line containing a string TTT, the sentence that Mr.Colorful believed the speaker originally wanted to say.

输出描述:

If in the log SSS there exists a weird sentence originated from TTT, please output two integers lll and rrr seperated by a space, denoting the location of the longest weird sentence (the string is 1-indexed). You need to ensure that lll is minimized.

Otherwise, output −1-1−1.

示例1

输入

复制aabbbbcabbc abbc

aabbbbcabbc
abbc

输出

复制2 7

2 7

说明

In sample 1, "abbbbcc" is a weird sentence of "abbc" with substring "bb" repeated.

示例2

输入

复制goodmorningiamarobrobothowareyousaythatagainiamaarobothhh iamarobot

goodmorningiamarobrobothowareyousaythatagainiamaarobothhh
iamarobot

输出

复制12 23

12 23

说明

In sample 2, "iamarobrobot" has "rob" repeated, and "iamaarobot" has "a" repeated. They both exist in the log. However, the previous one is longer.

示例3

输入

复制baaaaaaaaaaabaaaaaaa baaaa

baaaaaaaaaaabaaaaaaa
baaaa

输出

复制1 9

1 9

说明

In sample 3, "baaaaaaaa" has "aaaa" repeated.

示例4

输入

复制ninshufenmanjimabukenengzhedoushiyaoyaochuanbiexintamen zhedoushiyaochuan

ninshufenmanjimabukenengzhedoushiyaoyaochuanbiexintamen
zhedoushiyaochuan

输出

复制25 44

25 44

示例5

输入

复制queshilidadapu lidapu

queshilidadapu
lidapu

输出

复制7 14

7 14

问题

给定文本串SSS和模式串TTT，求SSS的一个最长子串，使得其为TTT重复其某个子区间的结果。

题解

KMP

对SSS正向做一次TTT的匹配，记录SSS每个前缀preipre_iprei​尾部能匹配到的TTT最长的前缀，记做fif_ifi​。

对SSS逆向做一次TTT的匹配，记录SSS每个后缀sufisuf_isufi​前部能匹配到的TTT最长的后缀，记做gig_igi​。 

如果fi+gi+1>∣T∣f_i + g_{i + 1} > |T|fi​+gi+1​>∣T∣，则可以更新答案。

时间复杂度O(∣S∣+∣T∣)O(|S| + |T|)O(∣S∣+∣T∣)

吐槽

其实这题代码很短，出题人和验题人都认为是Medium Easy或者Medium难度，但很奇妙的是内榜和外榜都一直没人做这题，校内吹了一堆F的气球没发出去。感觉榜有些歪？

虽然说题解是KMP，但实际过题方法众多。我的某个队友写了哈希+二分，另一个因为没带SAM板子干脆就没写，真是绝活。

 

//思路就是一个一个找就是遇到有可能的情况逐一排查但这题的核心亮点是对重复串的前缀，后缀处理法，这个思想是比较有意思的，就是一般都是想着如何从正面一举击破，而前后插刀，比较强

待我水平高了再来，加油。