---恢复内容开始---
https://www.jisuanke.com/contest/2226/173340
计算课的练习，今天从上午到晚上吃完饭一直在写这个题。
先看数据量，判断是否可以暴力穷举。n最大10w，互相比较每两个字符串要（1+10w）/2*10w大概50亿次，
但是这个数还要再乘上两个字符串比较时所用的“=”操作符函数的用的时间，这个函数时间复杂度与字符串长度正相关。
题中字符串长度最大为10；即最大数据500亿，时间两秒，计算机cpu双2.5ghz ，每秒大概运算几十亿次，所以排除；
然后直接的思路就是想到如果有字符串aba ba a，则a时ba的后缀，且如果ba是aba的后缀，则a一定是aba的后缀。
也就是说，从小向大找的话，以最小的字符串a为一级字符串，找到所有以a为后缀的二级字符串~以此类推到n级字符串，
且无以第n级字符串为后缀的字符串，则该级字符串后缀次数为1，那么该字符串的n-1级后缀字符串的后缀出现次数就是所有n级
后缀次数之和。以此类推Num[n-1](只是n级中的一个)=Num[n1]+Num[n2]+……+Num[nm];上述n1~nm都是以相应n-1为后缀的。
明显的递归结构，把递归条件和递归分析出来就开始写，于是：
结果果不其然超时了，超时了大概一秒，因为递归的多层调用太慢了，所以想当然的想把递归想用动态规划之类的方式改成循环
#include<iostream> #include<string> #include<vector> #include<stack> #include<algorithm> #define Data_Max 150000 #define rep(i,n,t) for(int i=(n);i<(t);i++) #define per(i,n,t) for(int i=(n);i>(t);i--) #define mms(a,b) memset(a,(b),sizeof(a)) //#define vector<string>::iterator It using namespace std; int Book[Data_Max]; bool comp(pair<string, int> a, pair<string, int> b) { return a.first.size() < b.first.size(); } int main() { vector<pair<string, int>> Input; int n; mms(Book, 0); rep(i, 0, Data_Max) Book[i]++; cin >> n; rep(i, 0, n) { string Temp; cin >> Temp; Input.push_back(make_pair(Temp, i)); } sort(Input.begin(), Input.end(), comp); int now = 0; int j = 1; int Booknumber; vector<vector<int>> Same; vector<int> S; while (Input.size()) { vector<int> Temp; Temp.push_back(Input[now].second); for (; j < Input.size(); j++) { int l1 = Input[now].first.size(), l2 = Input[j].first.size(); if (Input[j].first == Input[now].first) { Book[Input[now].second]++; Temp.push_back(Input[j].second); Input.erase(Input.begin() + j); j--; } else if (Input[now].first == Input[j].first.substr((l2 - l1), l1)) { //cnt++; S.push_back(j); now = j; if (Temp.size() > 1) { Same.push_back(Temp); Temp.push_back(Input[now].second); } Temp.clear(); } } if (S.size()) { j = S.back(); Booknumber = Input[S.back()].second; S.pop_back(); Input.erase(Input.begin() + now); if (S.size()) { now = S.back(); } else { now = 0; } Book[Input[now].second] += Book[Booknumber]; } else { now = 0; j = 1; Input.erase(Input.begin()); } } rep(i, 0, Same.size()) { rep(j, 1, Same[i].size()) { Book[Same[i][j]] = Book[Same[i][0]]; } } //输出部分 rep(i, 0, n) cout << Book[i] << endl; return 0; }
结果改到了晚上能过一些数据，但是还是有错。
这时才反思自己是不是思路有问题，有这一天的时间比赛都比好几场了。
结果在网上找到了这个。。。。。https://blog.csdn.net/qq_41998938/article/details/86771555
??感谢这位同学的博客让我浪子回头！看完顿时感觉自己就是菜，是菜鸡，菜的一批，菜是原罪，我有罪！！
虽然确实想到了用关联类型来存储序号 pair<string,int> 怎么就没想到使用map呢？
反思过后，根本原因是因为练得少，用的少。看似远在天边，近在眼前。但是如果一直就没用过，那多近都没用。
map是一个存储key-value对的数组，可以使用key当作下标。set则为存储key的数组。它的key等于value；
翻开c++ primer377页，讲解map时所用的例子就是 map<string,int>型来存储电话本；讲的清清楚楚map不同于顺序容器，
map的下标可以是其他类型的数据。此外，关联容器map和set都是默认升序存储的。并且是默认无重复元素的。
一般用列表初始化的方式来定义关联容器，例如
set<string> exclude={"the" ,"but","and","or","an","a"};
map<string,string> authors={ {"Joyce","james"}, {"Austen","Jane"},{"Dickens","Charles"}};
通常set的用于查找某个元素是否在已知的set容器中，例如if(exclude.find(word)==exclude.end()){ ……}
成员函数find接收一个元素，若容器中存在该元素则返回指向该元素的迭代器。否则返回尾后。
知道后用了很简单的代码就解决了
#include<iostream> #include<vector> #include<map> #include<string> using namespace std; int main() { map<string, int> M; vector<string> S; int n; cin >> n; for (int i = 0; i < n; i++) { string temp; cin >> temp; S.push_back(temp); for (int j = 0; j < temp.size(); j++) { M[temp.substr(j)]++; } } for (int i = 0; i < n; i++) { cout << M[S[i]] << endl; } return 0; }
原文：https://www.cnblogs.com/worldcreator-zh/p/10498813.html