Substrings （C++ find函数应用）

佚名 6年前 (2019-04-12) 随笔 615人围观抢沙发百度已收录

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 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++ string 中的一些函数处理的，比使用C的逐个字符的遍历好写一些。贴一篇关于find函数的说明： https://www.cnblogs.com/wkfvawl/p/9429128.html

#include <iostream>
#include <string>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int main()
{
    int t,n,i,j,k;
    int mins;
    int pos,flag,flag1;
    string s[110];
    string key;
    string tem;
    string rev;
    cin>>t;
    while(t--)
    {
        cin>>n;
        pos=0;
        flag=1;
        mins=INF;
        for(i=0;i<n;i++)
        {
            cin>>s[i];
            if(s[i].length()<mins)
            {
                mins=s[i].length();
                pos=i;
            }
        }
        key=s[pos];
        for(i=mins;i>=1;i--)//子串长度
        {
            for(j=0;j+i-1<mins;j++)
            {
                tem=key.substr(j,i);//截取以j开头长度为i的子串
                rev=string(tem.rbegin(),tem.rend());//反向迭代器，翻转后的子串
                flag=1;
                flag1=1;
                for(k=0;k<n;k++)
                {
                   if(s[k].find(tem)==string::npos&&s[k].find(rev)==string::npos)
                   {
                       flag=0;
                       break;
                   }//没有找到这样一个子串
                }
                if(flag)//找到了一个子串
                {
                    cout<<i<<endl;
                    flag1=0;
                    break;
                }
            }
            if(!flag1)
            {
                break;
            }
        }
        if(flag1)
        {
            cout<<0<<endl;
        }
    }
    return 0;
}