The Dominator of Strings

Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1530 Accepted Submission(s): 531

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

Source
2017 ACM/ICPC Asia Regional Qingdao Online

　　　　这道题可以用ＳＴＬ过。。。。题意大概是要你找子字符串。如果存在一个字符串，这个字符串包含其他所有的字符串。那么输出这个字符串，否则输出NO。

代码：

#include<iostream>
#include<string>
using namespace std;

const int MAX = 200000 + 10;

string a[MAX];
string s;

bool is_dominator(const int n, const int idx)
{
    for (int i = 0; i < n; i++) {
        if (i == idx) continue;
        if (s.find(a[i]) == string::npos) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 0;
    cin >> t;
    while (t--) {
        int n = 0, idx = 0, maxLen = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i].length() > maxLen) {//如果存在符合题意的字符串，那么这个字符串越长越有可能是母串。
                maxLen = a[i].length();
                idx = i;
            }
        }
        s = a[idx];
        if (is_dominator(n, idx)) cout << s << endl;
        else cout << "No" << endl;
    }
    return 0;
}








//

　　　　嗯，今天2017-09-21 17:55:28，补上ＢＦ算法，至于ＫＭＰ还在学，学会后会继续补上ＫＭＰ算法。

ＢＦ算法：

/* *HDU 6208 *Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language * Accepted 6208 811MS 7332K 1134 B G++ */

#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<string> s;

bool BF(string&w, int u)
{
    int i = 0, j = 0, len = s[u].length(), wlen = w.length();
    while (i < len && j < wlen) {
        if (w[j] == s[u][i]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= wlen)return true;
    return false;
}

bool is_dominator(int u)
{
    int t = s.size();
    for (int i = 0; i < t; i++) {
        if (i!=u && !BF(s[i],u))return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);//不关了同步会超时。。。。
    cin.tie(0);
    int t = 0, n = 0;
    cin >> t;
    while (t--) {
        int maxlen = 0, u = 0, len = 0;
        cin >> n;
        s.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            len = s[i].length();
            if (maxlen < len) {
                maxlen = len;
                u = i;
            }
        }
        if (is_dominator(u)) cout << s[u] << endl;
        else cout << "No\n";
    }
    return 0;
}







//.

　　　　经过几天的学习，总算是把ＫＭＰ学了个大概，还有一些细节的东西没有完全弄懂，等我弄明白后会尝试写一下ＫＭＰ算法的详解。今天2017-09-24 11:36:50先补上这道题的ＫＭＰ解法。
　　　　

ＫＭＰ算法：

/* *Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language *Accepted 6208 748MS 7324K 1615 B G++ */
#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<string> str;
vector<int> Next;

void getNext(const int v)
{
    const string &w = str[v];
    int len = w.length();
    Next.resize(len + 1);
    Next[0] = -1;
    int i = 0, j = -1;
    while (i < len && j < len) {
        if (j == -1 || w[i] == w[j]) {
            i++;
            j++;
            if (w[i] != w[j]) Next[i] = j;
            else Next[i] = Next[j];
        }
        else j = Next[j];
    }
}


bool KMP(const int u, const int v)//u->主串，v->模式串
{
    const string &w = str[v], &s = str[u];
    int wlen = w.length(), slen = s.length();
    int i = 0, j = 0;
    getNext(v);
    while (i < slen && j < wlen) {
        if (j == -1 || s[i] == w[j]) {
            i++;
            j++;
        }
        else j = Next[j];
    }
    if (j >= wlen) return true;
    return false;
}

bool is_Dominator(const int u)
{
    int t = str.size();
    for (int i = 0; i < t; i++) {
        if (i != u && !KMP(u, i)) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 0;
    cin >> t;
    while (t--) {
        int n = 0, maxlen = 0, u = 0, len = 0;;
        cin >> n;
        str.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> str[i];
            len = str[i].length();
            if (len > maxlen) {
                maxlen = len;
                u = i;
            }
        }
        if (is_Dominator(u)) cout << str[u] << endl;
        else cout << "No\n";
    }
    return 0;
}







///