HDU-6208 The Dominator of Strings(查找子串string)

                                    The Dominator of Strings

                      Time Limit: 3000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
                                             Total Submission(s): 5188    Accepted Submission(s): 1718
Problem Description

Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string S is dominated by T if S is a substring of T.

 Input

The input contains several test cases and the first line provides the total number of cases.
For each test case, the first line contains an integer N indicating the size of the set.
Each of the following N lines describes a string of the set in lowercase.
The total length of strings in each case has the limit of 100000.
The limit is 30MB for the input file.

 Output

For each test case, output a dominator if exist, or No if not.

 Sample Input

3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac

Sample Output

youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
abcde
No

http://acm.hdu.edu.cn/showproblem.php?pid=6208

题意：

给你n个字符串，问里面是否有一个字符串，它包含了全部的字符串。也就是所有的字符串都是这个字符串的字串。有的话输出该字符串，没有输出No.

思路：

先找出最长的字符串，那么肯定是主串。可以用string中的find来查找其他字符串是否在该最长的字符串中。有一种特殊情况，如果字符串的长度相等，那么只要有其中一个不相等，输出No。

string.find的用法：

查找字符串a是否包含子串b,
不是用strA.find(strB) > 0而是strA.find(strB) != string:npos
string::size_type pos = strA.find(strB);

 find函数返回类型 size_type
string s("1a2b3c4d5e6f7g8h9i1a2b3c4d5e6f7g8ha9i");
string flag;
string::size_type position;

//find 函数 返回jk 在s 中的下标位置 
position = s.find("jk");
 if (position != s.npos)  //如果没找到，返回一个特别的标志c++中用npos表示，我这里npos取值是4294967295，
 {
  cout << "position is : " << position << endl;
 }
 else
 {
  cout << "Not found the flag" + flag;
 } 

//find 函数 返回flag 中任意字符 在s 中第一次出现的下标位置
 flag = "c";
 position = s.find_first_of(flag);
 cout << "s.find_first_of(flag) is : " << position << endl;

 //从字符串s 下标5开始，查找字符串b ,返回b 在s 中的下标
 position=s.find("b",5);
 cout<<"s.find(b,5) is : "<<position<<endl;

//查找s 中flag 出现的所有位置。
 flag="a";
 position=0;
 int i=1;
 while((position=s.find_first_of(flag,position))!=string::npos)
 {
  //position=s.find_first_of(flag,position);
  cout<<"position  "<<i<<" : "<<position<<endl;
  position++;
  i++;
 }

 //查找flag 中与s 第一个不匹配的位置
 flag="acb12389efgxyz789";
 position=flag.find_first_not_of (s);
 cout<<"flag.find_first_not_of (s) :"<<position<<endl;


 //反向查找，flag 在s 中最后出现的位置
 flag="3";
 position=s.rfind (flag);
 cout<<"s.rfind (flag) :"<<position<<endl;
}

 

说明：

1.  如果string sub = ”abc“；

              string s = ”cdeabcigld“；

     s.find(sub) , s.rfind(sub) 这两个函数，如果完全匹配，才返回匹配的索引,即：当s中含有abc三个连续的字母时，才返回当前索引。

     s.find_first_of(sub),   s.find_first_not_of(sub),   s.find_last_of(sub),  s.find_last_not_of(sub)  这四个函数，查找s中含有sub中任意字母的索引。

2.  如果没有查询到，则返回string::npos，这是一个很大的数，其值不需要知道。

 

代码：

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 100010;
string s[Maxn];
int main()
{
	cin.sync_with_stdio(false);//没有它会超时。使用它，可以让cin,cout的速度与scanf,printf差不多
	int t;
	cin >> t;
	while(t--){
		int n; 
		cin >> n;
		int len;
		int maxid = -1;
		int Max = -1;
		int flag = true;
		for(int i = 0; i < n; i++) {
			cin >> s[i];
			len = s[i].length();
			if(len > Max || Max == -1) {
				Max = len;
				maxid = i; 
				flag = true;
			} 
			else if(len == Max && s[maxid] != s[i])
				flag = false;
		}
		if(flag) {
			for(int i = 0; i < n ; i++) {
				if(s[maxid].find(s[i]) == s[i].npos) {
					flag = false;
					break;
				}
			}
		}	
		if(flag)
			cout << s[maxid] << endl;
			
		else 	
			cout << "No" << endl; 
	}
	
	return 0;
}