题目描述
给你一个由小写英文字母组成的字符串 S, S 有多少个不同的非空子串？
子串是连续的子序列。例如，xxx是yxxxy的子串，但不是xxyxx的子串。
数据范围：S 是长度在 1 和 100 之间(含)的字符串，由小写英文字母组成。
题解
我认为这道题放在普及组的话，非常适合放在第一题和第二题之间，当我们看到数据范围是100的话，这个最大可承受的时间复杂度是\(O(n^4)\),所以我们可以枚举。这里要求的是所以不同的非空子串的长度，所以我们需要在每个长度上都找出是否有相同的子串，比如说yay,在长度为1的时候，就是相同的非空子串
所以第一个维度我们应该先枚举长度len，第二个维度枚举起点i，那么终点我们就知道了，是j=i+len，对于每一个\((i,j)\)之间的子串，我们来比较长度为len的，起点k在\([1-i-1]\)的所有子串，是否和\([i,len]\)的子串相同，所以我们枚举len，枚举起点i，枚举子集的起点k，比较字符串是否相等，时间复杂度是\(o(n^4)\),代码如下：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
char s[maxn];
int ans;
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
for(int len=1;len<=n;len++){
for(int i=1;i<=n;i++){
if(i+len-1>n) break;
int cnt=0;
for(int j=1;j<i;j++){
int k=0;
while(s[i+k]==s[j+k]&&k<len) k++;
if(k==len) {
cnt=1;
break;
}
}
if(cnt==0) {
//cout<<i<<endl;
ans+=1;
}
}
}
cout<<ans<<endl;
return 0;
}