HDU-1238 Substrings
程序员文章站
2022-04-30 20:35:14
...
HDU-1238 Substrings
题目链接:HDU-1238
题目大意:问给定个数的一些字符串中 最长的公共子串有多长 子串反过来匹配也算
解题思路:从最短的字符串进行暴力切割 取到他的各种子串 然后将此子串的原形式和反向形式与给定字符串进行匹配识别 如果都含有就输出长度就好了 匹配过程用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;
}
推荐阅读
-
SPOJ8222 NSUBSTR - Substrings(后缀自动机)
-
cf914F. Substrings in a String(bitset 字符串匹配)
-
SPOJ8222 NSUBSTR - Substrings(后缀自动机)
-
647. Palindromic Substrings
-
CF1276F Asterisk Substrings【endpos后缀的本质不同串个数(dfs序并)】
-
【后缀数组 不同的字串个数】SPOJ - SUBST1 New Distinct Substrings
-
SPOJ Distinct Substrings (后缀数组,不相同的子串个数)
-
647. Palindromic Substrings
-
Substrings Sort
-
D. A and B and Interesting Substrings(前缀和+思维)