HDU-1238-Substrings(求公共子串)

博主链接

题目链接

题意：

找出所有字符串中共同拥有的一个子串，该子串（正、逆字符）是任何一个母串的子串，求该子串的最长长度。

题解：

利用string库里的find函数+STL中的reverse反转函数。先找出最短的母串，即该符合要求的子串肯定在这个母串中，即在从长到短，从最短母串中取子串，在子串正反去查看是否符合要求。

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
string s[120];
int main() {
	int t;
	scanf("%d", &t);
	while ( t--) {
		int n,sub;
		scanf("%d", &n);
		int len = 1000;
		for (int i = 0; i < n; i++) {
			cin >> s[i];
			if (s[i].size() < len)len = s[i].size(), sub = i;
		}
		int maxn = 0;
		for (int i = s[sub].size(); i > 0; i--) {
			for (int j = 0; j <= s[sub].size(); j++) {
				string s1, s2;
				s1 = s[sub].substr(j, i);
				s2 = s1;
				reverse(s2.begin(), s2.end());   //反转
				int k;
				for (k = 0; k < n; k++) {
					if (s[k].find(s1, 0) == -1 && s[k].find(s2, 0) == -1)break;
					
				}
				if (k == n && maxn < s1.size())maxn = s1.size();
			}
		}
		printf("%d\n", maxn);
	}
	return 0;
}