Substrings Sort（cf 988B)（strstr函数的使用）

题目链接：

http://codeforces.com/problemset/problem/988/B

题面：

翻译：

你有n个字符串。每个字符串由小写英文字母组成。重新排列给定的字符串，对于每个字符串，放在它前面的所有字符串都是它的子字符串。
字符串的子串字符串b如果可以选择连续几个字母b以这样一种方式,他们形成一个。例如,字符串”为“包含子字符串在字符串“codeforces”、“为”和“因此”,但不包含子字符串在字符串“四”、“fofo”和“学院”。

输入

第一行包含一个整数n(1≤n≤100)——字符串的数量。
接下来的n行包含给定的字符串。每个字符串中的字母数从1到100，包括100。每个字符串由小写英文字母组成。
有些字符串可能是相等的。

输出

如果无法按要求的顺序对n个给定的字符串重新排序，请打印“NO”(不带引号)。
否则按要求顺序打印“YES”(不带引号)和n个给定字符串。

思路：

在讲这个题目之前，先扩展一个知识 strstr函数

strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串；否则，返回NULL。

这道题目是首先给你n个字符串，让你重新排序，判断对于每个字符串是否重新在它前面的所有字符串都是这个字符串的子串，就意味着在这个字符串前面的字符串必须要在当前的字符串重新过，这时候我们就可以想起来一个字符串函数strstr，这个函数是一个字符串是否属于另一个字符串的子串，我们就可以先继续排序，排序的话我们就可以根据每个字符串的长度来进行排序，作为一个字符串的子串长度一定小于等于母串，所有我们可以定义一个结构体变量，把字符串和字符串对应的长度放在一个结构体里面，后面对其这个结构体按照字符串的长度从小到大排序，然后我们就一个个遍历判断上一个字符串是否为下一个字符串的子串，如果出现一个不满足的，那么就意味着不成立，输出no。

参考代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
#define ll long long ;
struct node//定义一个结构体，把字符串和字符串对应的长度定义为一个结构体变量
{
    int len;//字符串长度
    char s[10000];//字符串
}str[10000];
bool cmp(node a,node b)//把结构体按照字符串长度从短到长进行排序
{
    return a.len<b.len;
}
int main()
{
    int n,i,flag=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        cin>>str[i].s;//输入字符串
        str[i].len=strlen(str[i].s);//存储字符串的长度
    }
    sort(str,str+n,cmp);//对其进行排序
    for(i=1;i<n;i++)
    {
        if(strstr(str[i].s,str[i-1].s)==0)//如果出现上一个字符串在当前字符串未查找到，那么意味着上一个字符串不是当前字符串的子串，就进行标记，同时直接跳出循环
        {
            flag=1;
            break;
        }
    }
    if(flag==1)//如果被标记了，就证明出现给上一个字符串不是下一个字符串的子串的情况，就直接输出no
    {
        cout<<"NO"<<endl;
    }
    else//如果满足就同时输出yes，在把排序完了的字符串输出
    {
        cout<<"YES"<<endl;
        for(i=0;i<n;i++)
        {
            cout<<str[i].s<<endl;
        }
    }
}