HDOJ 1238 Substrings 【最长公共子串】
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11430 Accepted Submission(s): 5490
Problem Description You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output There should be one line per test case containing the length of the largest string found.
Sample Input
2 3 ABCD BCDFF BRCD 2 rose orchid
Sample Output
2 2
题意 给出一系列字符串 求出这些字符串中的最长公共子串
思路 可以用C++ STL 里面的东西 去找子串 因为题目要求 是可以逆字符串的 所以可以用reverse 然后 查找可以用find
AC代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; string s[maxn]; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int i, j, k; int sub; int len = MAXN; for (i = 0; i < n; i++) { cin >> s[i]; if (s[i].size() < len) { len = s[i].size(); sub = i; } } int ans = 0; for (i = s[sub].size(); i > 0; i--) { for (j = 0; j < s[sub].size() - i + 1; j++) { string s1, s2; s1 = s[sub].substr(j, i); s2 = s1; reverse(s2.begin(), s2.end()); for (k = 0; k < n; k++) { if (s[k].find(s1, 0) == -1 && s[k].find(s2, 0) == -1) break; } if (k == n && s1.size() > ans) ans = s1.size(); } } cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433361.html
相关资源：JAVA上百实例源码以及开源项目