连续重复子字符串查找

╰+攻爆jí腚メ 2022-05-22 11:20 258阅读 0赞

# 本题来自2018深信服提前批笔试编程题部分。 #

### 题目描述： ###

一个重复子字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。

给定任意字符串，请帮小强找出其中的最长重复子串。

### 输入描述： ###

输入一个字符串s，其中s长度小于1e4而且只包含数字和字母。

### 输出描述： ###

输出一个整数，表示s的最长重复子串长度，若不存在则输出0.

### 示例： ###

输入

xabcabcx

输出

分析：主要用到的是字符串的后缀子串，因为后缀子串能间接表示所有的子字符串，java实现如下，为了解答更清楚，没有按照题目要求输出，这里输出更加详细，也更加利于看懂。

import java.util.Scanner;
    
    public class FindRepeatedString {
    	public static void main(String[] args){
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){
    			String s = sc.next();
    			String[] sub = new String[s.length()];
    			//存储所求的最长子字符串，可能有多个
    			String[] res = new String[s.length()];
    			//存储所求的最长子字符串的长度
    			int maxLength = 0;
    			//存储所求的最长子字符串出现的个数
    			int maxCount = 0;
    			//存储后缀子串，后缀字符串能间接表示所有的子字符串
    			//每个后缀字符串的所有前缀字符串合起来即是所有子字符串
    			for(int i = 0; i < s.length(); i++)
    				sub[i] = s.substring(i);
    			//i为子字符串的长度
    			for(int i = 1; i <= s.length()/2; i++){
    				//存储每个长度的重复子字符串的个数
    				int Count = 0;
    				for(int j = 0; 2*i+j <= s.length(); j++){
    					if(sub[j].substring(0, i).equals(sub[j+i].substring(0, i))){					
    						maxLength = 2*i;
    						res[Count] = sub[j].substring(0, 2*i);
    						Count ++;
    						maxCount = Count;
    					}
    				}
    			}
    			if(maxCount == 0)
    				System.out.println(0);
    			else{
    				System.out.println(maxLength);
    				for(int i = 0; i < maxCount; i++)
    					System.out.println(res[i]);
    			}
    		}
    	}
    }

下面给出C++的实现，这里只输出了最后一个匹配的最长的子字符串。假如存在多个最长的子字符串并没有一一给出，若想像前面java实现一样全部列出来只需稍作修改即可。

#include <iostream>
    #include <cstring>
    #include <utility>
    #include <string>
    #include <vector>
    using namespace std;
    
    vector<pair<int, string>> fun(const string& str)
    {
    	vector<string> subs;
    	vector<pair<int, string>> res;
    	int len = str.size();
    	for (int i = 0; i < len; i++)
    	{
    		subs.push_back(str.substr(i));
    	}
    
    	int length;
    	string sub;
    
    	//i为子串的长度
    	for (int i = 1; i <= len/2; i++)
    	{
    		for (int j = 0; 2*i + j <= len; j++)
    		{
    
    			if (subs[j + i].substr(0, i) == subs[j].substr(0, i))
    			{
    				length = 2 * i;
    				sub = subs[j].substr(0, i) + subs[j].substr(0, i);
    				res.clear();
    				res.push_back(make_pair(length, sub));
    			}		
    			//res.push_back(make_pair(length, sub));
    		}
    	}
    
    	return res;
    }
    
    int main()
    {
    	string str;
    	vector<pair<int, string>> res;
    	while (cin >> str)
    	{
    		res = fun(str);
    		for (auto it = res.begin(); it != res.end(); it++)
    		{
    			cout << it->second << ":" << it->first << endl;
    		}
    	}
    
    	return 0;
    }