B – Substrings Sort

Problem description

You are givennn strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are itssubstrings.

Stringais asubstring of stringb if it is possible to choose severalconsecutiveletters inb in such a way that they forma. For example, string "for" is contained as asubstring in strings "codeforces", "for" and "therefore", but is not contained as asubstring in strings "four", "fofo" and "rof".

Input

The first line contains an integernn (1≤n≤100) — the number of strings.

The nextnn lines contain the given strings. The number of letters in each string is from1to100, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output

If it is impossible to reordernn given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) andnn given strings in required order.

Examples

Input

5aabaabacababaaba

Output

YESabaabaabaabacaba

Input

5aabacababaabaabab

Output

NO

Input

3qwertyqwertyqwerty

Output

YESqwertyqwertyqwerty

Note

In the second example you cannot reorder the strings because the string "abab" is not asubstring of the string "abacaba".

解题思路：C语言中strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回str2在str1中首次出现的地址；否则，返回NULL。了解了这个函数，这道题就非常简单。只要将字符串的长度按升序排列，然后从第二个字符串开始依次检查当前字符串是否含有前一个字符串，即如果strstr(str1,str2)都不为NULL，就满足所有条件输出"YES"，否则输出"NO"。

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct NODE{
 4     char str[105];
 5     int len;
 6 }node[105];
 7 bool cmp(NODE a,NODE b){return a.len<b.len;}
 8 int main(){
 9     int n;
10     cin>>n;getchar();
11     for(int i=0;i<n;++i){
12         cin>>node[i].str;
13         node[i].len=strlen(node[i].str);
14     }
15     sort(node,node+n,cmp);
16     bool flag=false;
17     for(int i=1;i<n;++i)
18         if(strstr(node[i].str,node[i-1].str)==NULL){flag=true;break;}
19     if(flag)cout<<"NO"<<endl;
20     else{
21         cout<<"YES"<<endl;
22         for(int i=0;i<n;++i)
23             cout<<node[i].str<<endl;
24     }
25     return 0;
26 }

C++的string类提供了字符串中查找另一个字符串的函数find。其重载形式为：string::size_type string::find(string &);功能为在string对象中，查找参数string类型的字符串是否存在，如果存在，返回起始位置。不存在则返回 string::npos。因此，此题还可以用这个来判断。

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct NODE{
 4     string str;
 5     int len;
 6 }node[105];
 7 bool cmp(NODE a,NODE b){return a.len<b.len;}
 8 int main(){
 9     int n;
10     cin>>n;getchar();
11     for(int i=0;i<n;++i){
12         cin>>node[i].str;
13         node[i].len=node[i].str.length();
14     }
15     sort(node,node+n,cmp);
16     bool flag=false;
17     for(int i=1;i<n;++i)
18         if(node[i].str.find(node[i-1].str)==string::npos){flag=true;break;}
19     if(flag)cout<<"NO"<<endl;
20     else{
21         cout<<"YES"<<endl;
22         for(int i=0;i<n;++i)
23             cout<<node[i].str<<endl;
24     }
25     return 0;
26 }

原文链接: https://www.cnblogs.com/acgoto/p/9124912.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍