欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NSUOJ - 找子串 - Problem 2701

程序员文章站 2022-07-12 15:52:37
...

题目来源 http://acm.ccniit.com/problem.php?cid=1199&pid=11

一.题目内容

给你n个字符串,然后随后m行查询,对于每个查询字符串s,输出结果
结果: s是多少个str[i]的子串,所有存在,并且输出str[i]的字典序最大的串

Input

输入n(1<=n<=10000),紧接著n行为str[i]的字符串。输入m(1<=m<=50000)
接着m行查询,输入字符串s


(规定所有的字符串长度不超过10)

Output

对应每行输入,输出一行,如果每个s2,如果不在s1中所有的子串出现则输出0,否则输出在所有串中出现子串的次数,以及出现在字典序最大的字符串是哪个

Sample Input Copy

8
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
16
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa

Sample Output Copy

8 aaaaaaaa
7 aaaaaaaa
6 aaaaaaaa
5 aaaaaaaa
4 aaaaaaaa
3 aaaaaaaa
2 aaaaaaaa
1 aaaaaaaa
8 aaaaaaaa
7 aaaaaaaa
6 aaaaaaaa
5 aaaaaaaa
4 aaaaaaaa
3 aaaaaaaa
2 aaaaaaaa
1 aaaaaaaa

二.解题思路

输入一次跑一次循环会超时的,题中说字符串长度不超过10,可以枚举字符串的子串,需要注意一个字符串中相同子串只算一个,有子串相同的将字符串比较,子串出现过直接输出个数和最大的有此子串的最大字符串,否则输出0。

假设:string s = "0123456789"; 

string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾:sub1 = "56789"

string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位:sub2 = "567"

map的内部默认按照key从小到大进行排序 ,unordered_map 内部无序效率高。

三.代码

#include<bits/stdc++.h>
using namespace std;
string shuchu[50009],a,b,s;
unordered_map<string,string>p;
unordered_map<string,int>q;
unordered_map<string,bool>z;
int main()
{
    int n,m,num,t,k;
    while (scanf("%d",&n)!=EOF)
    {  p.clear(),q.clear();
        for (int i = 0; i < n; ++i) {
        cin>>a;
        for (int j = 0; j <a.size() ; ++j) {
            for (int l = 1; l <=a.substr(j).size() ; ++l) {
              if (!z[a.substr(j,l)])
              {
                  q[a.substr(j,l)]++;z[a.substr(j,l)]=true;
                  p[a.substr(j,l)]=max(p[a.substr(j,l)],a);
              }
            }
        }z.clear();
    }scanf("%d",&m);
    for (int i = 0; i < m; ++i) {
        cin>>shuchu[i];
    }
    for (int i = 0; i < m; ++i) {
        if (q[shuchu[i]])
            printf("%d ",q[shuchu[i]]),cout<<p[shuchu[i]]<<endl;
        else printf("0\n");
    }
    }
}

相关标签: STL 字符串