计蒜客蓝桥杯省赛模拟G

题目

一天蒜头君得到 n 个字符串 si，每个字符串的长度都不超过 1010。

蒜头君在想，在这 n 个字符串中，以 si 为后缀的字符串有多少个呢？

输入格式

第一行输入一个整数 n。

接下来 n 行，每行输入一个字符串 si。

输出格式

输出 n 个整数，第 i 个整数表示以 si 为后缀的字符串的个数。

数据范围

对于 50%50% 的数据，1≤n≤10³1≤n≤10³。

对于 100%100% 的数据，1≤n≤10⁵1≤n≤10⁵。

所有的字符串仅由小写字母组成。

Sample Input

3

ba

a

aba

Sample Output

起初思路

我最开始真的很单纯啊！纯暴力！以为蓝桥杯都是暴力。。。先开始是灵机一动，把字符串反转一下，找后缀就变成了找前缀了，然后用find函数去查找其他的字符串中是否有当前串，如果有并且返回的是0，说明就是一样的前缀，交了一发，妥妥的TLE。

TLE代码

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e5;

//@start: 2020-10-06 08:10:15

string s[maxn];

int a[maxn];

int main()

{

    int n;

    cin>>n;

    for(int i=0;i<n;i++){

        a[i]=1;

        cin>>s[i];

        reverse(s[i].begin(),s[i].end());

    }

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            if(i==j) continue;

            if(s[j].find(s[i])==0) a[i]++;

        }

    }

    for(int i=0;i<n;i++){

        printf("%d\n",a[i]);

    }

    return 0;

}

正确解法

官方给的做题思路是用map<string,int>来存后缀出现的次数。思路很简单，每输入一个字符串，就遍历这个字符串所有的后缀，然后保存在map中，对应的int自加。

正确代码

#include <iostream>

#include <algorithm>

#include <map>

using namespace std;

const int N=1e5;

string s[N];

int main()

{

    map<string,int> mp;

    int n;

    cin>>n;

    for(int i=0;i<n;i++){

        cin>>s[i];

        for(int j=0;j<s[i].size();j++){

            mp[s[i].substr(j)]++;

        }

    }

    for(int i=0;i<n;i++){

        cout<<mp[s[i]]<<endl;

    }

    return 0;

}

string::substr()函数原型

std::__cxx11::string std::__cxx11::string::substr(std::size_t __pos, std::size_t __n = 4294967295U) const

@brief Get a substring.

@param __pos Index of first character (default 0).

@param __n Number of characters in substring (default remainder).

@return The new string.

@throw std::out_of_range If __pos > size().

Construct and return a new string using the @a __n characters starting at @a __pos. If the string is too

short, use the remainder of the characters. If @a __pos is

beyond the end of the string, out_of_range is thrown.

翻译成人话：

s.substr(pos,n);

返回的是从字符串s中从pos位置开始，长度为n的子串。

当然第二个参数也可不传，默认就是返回从pos位置到字符串的结尾。

样例

来个例子立马看懂：

string s="1234";

cout<<s.substr(1)<<endl;//打印234

cout<<s.substr(1,2)<<endl;//打印23