NC142 最长重复子串

题目描述

一个重复字符串是由两个相同的字符串首尾拼接而成,例如abcabc便是长度为6的一个重复字符串,而abcba则不存在重复字符串。
给定一个字符串,请编写一个函数,返回其最长的重复字符子串。
若不存在任何重复字符子串,则返回0。

想法

没想到什么特别的解法,直接暴力= = 题目中说是重复子串,其实规定了是重复一次的,多次的不算,所以暴力就o(N^3), 勉强接受了。

    bool judge(string& a,int s,int len)
    {
        for(int i=s;i<s+len;i++)
        {
            if(a[i]!=a[i+len])
                return false;
        }
        return true;
    }
    int solve(string a) {
        int n = a.size();
        int len=n/2;
        int max_len =0;

        for (int i=len;i>0;i--) {
            for (int s=0;s<=n-i-i;s++) {
                if (judge(a,s,i)) {
                    return 2*i;
                }
            }
        }
        return 0;
    }