【Leetcode刷题Python】子数组查找

深信服公司的算法笔试题

1 题目

一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。 给定任意字符串，请帮小强找出其中的最长重复子串。 示例

输入 “ababc” 输出 4 说明 abab为最长的重复字符子串，长度为4

2 解析

子串问题一般都是用滑动窗口解决，这里就是一个典型的例子，

• 我们先将字符串从中间分开，看成两个连续的窗口，最大窗口的长度是字符串长度的一半，函数比较窗口中的内容是否相等，如果相等，返回true，此时的最长重复子串长度等于一个窗口的长度的两倍，即2*i;否则继续移动窗口，移动步数的边界是字符串长度减去此时的两个窗口长度；
• 在这一层窗口长度中找不到重复子串则缩小窗口长度，重复步骤2，直到窗口长度缩小至0，循环结束

3 Python 实现

def solve(s):
    if s=='':
         return 0
    mid=int(len(s)/2)
    # 记录窗口长度
    res=0
    # 窗口长度最长为一半，且不断减小
    for i in range(mid,-1,-1):
        # j不仅控制着窗口内容的比较，而且控制着窗口的移动，窗口移动的边界条件是字符串长度减去当前的一个窗口长度
        for j in range(len(s)-i):
            # 比较两个窗口中的字符                                    
            if s[j]==s[j+i]:
                res+=1
            # 一旦出现一个字符不相等时，窗口长度置0，从下一个字符开始遍历
            else:
            	res=0;
            # 当结果等于当前一个窗口的长度时，返回窗口长度的两倍
            if res==i:
                return 2*i
    return 0
print(solve(str(input())))