欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU-1238 Substrings

程序员文章站 2022-04-30 20:35:14
...

HDU-1238 Substrings

题目链接:HDU-1238
HDU-1238 Substrings
题目大意:问给定个数的一些字符串中 最长的公共子串有多长 子串反过来匹配也算

解题思路:从最短的字符串进行暴力切割 取到他的各种子串 然后将此子串的原形式和反向形式与给定字符串进行匹配识别 如果都含有就输出长度就好了 匹配过程用kmp 觉得暴力匹配会超时

代码块:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int nex[1005];

void getNext(string strA){
	int len = strA.length();
//	cout<<"len = "<<len<<endl;
	nex[0] = 0;
	int i = 1, j = 0;
	while(i < len){
		if(strA[i] == strA[j]){
			nex[i++] = ++j;
		}else if(j != 0){
			j = nex[j - 1];
		}else{
			nex[i++] = 0;
		}
	}
}

int kmp(const string strStr, const string strSub){
	int lenStr = strStr.length();
	int lenSub = strSub.length();
	int i = 0, j = 0;
	while(i < lenStr && j < lenSub){
		if(j == 0 || strStr[i] == strSub[j]){
			if(strStr[i] == strSub[j]){
				j++;
			}
			i++;
		}else{
			j = nex[j - 1];
		}
	} 
	if(j == lenSub) return i - j;
	else return -1;
} 

int main(){
	int n;
	cin>>n;
	while(n--){
		int k;
		cin>>k;
		string strA[105];
		int minSize = 9999999;
		int minIndex = 0;
		for(int i = 0; i < k; i++){
			cin>>strA[i];
			if(strA[i].length() < minSize){
				minSize = strA[i].length();
				minIndex = i;
			}
		}
		int res = 0;
		for(int i = minSize; i > 0; i--){// 字串长度 
			for(int j = 0; j <= minSize - i; j++){ //起始位置 
				string strSub = "";
				for(int q = j; q < i + j; q++){
					strSub += strA[minIndex][q];
				}
//				cout<<"minSize = "<<minSize<<endl;
//				cout<<"strSub = "<<strSub<<"|"<<endl;
				// 这里已经得到暴力得来的字串 字串顺序从长到短 从前到后
				// 进去查找步骤 
				getNext(strSub); 
//				for(int g = 0; g < minSize + 1; g++){
//					cout<<"--"<<next[g]<<endl;
//				}
				bool isT = true;
				for(int q = 0; q < k; q++){
					int value1 = kmp(strA[q], strSub);
					// 将strA[q]反序查找 
					string strcp = "";
					for(int c = strA[q].length() - 1; c >= 0; c--){
						strcp += strA[q][c];
					} 
					int value2 = kmp(strcp, strSub);
//					cout<<"value = "<<value<<endl;
					if(value1 == -1 && value2 == -1){
						isT = false;
						break;
					}
				} 
				if(isT){
					res = i;
					goto c;
				}
				memset(nex,0,sizeof(nex));
			}
		}
		c:{
			cout<<res<<endl;
		};
	}
	return 0;
}