本文主要是介绍HDU-5510 Bazinga（利用strstr函数找子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路借鉴：https://blog.csdn.net/floraqiu/article/details/78512986
Problem Description
Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.
For n given strings S1,S2,⋯,Sn , labelled from 1 to n , you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si .
A substring of a string Si is another string that occurs in Si . For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".
Input
The first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,⋯,Sn .
All strings are given in lower-case letters and strings are no longer than 2000 letters.
Output
For each test case, output the largest label you get. If it does not exist, output −1 .
Sample Input
4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc
Sample Output
Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3
思路：strstr（a,b）是当b是a的子串事，返回在a中第一次出现的位置；如果b不是a的子串返回NULL；
这道题用常规两重循环TLE了，应该利用子串的传递性：如果每一个字符串前面相邻一个都是它的子串，那么最小的那个也一定是这个最大字符串的子串。如果找到一个字符串的前一个字符串不是它的子串，那么开始往后查找是不是之前循环过的那些大字符串的子串。记录下最大的序号ans。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
char s[505][2005];
int main()
{int t,n,ans,flag=1;cin>>t;while(t--){cin>>n;ans=-1;for(int i=0;i<n;i++){cin>>s[i];}for(int i=n-1;i>=1;i--){if(!strstr(s[i],s[i-1])){ans=max(ans,i);for(int j=i+1;j<n;j++){if(!strstr(s[j],s[i-1]))ans=max(ans,j);}}}cout<<"Case #"<<flag++<<": ";if(ans==-1)cout<<ans<<endl;elsecout<<ans+1<<endl;}return 0;
}
这篇关于HDU-5510 Bazinga（利用strstr函数找子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
