每日一算法（4）

每日一算法（4） 每日算法篇-蓝桥真题篇

“有时候真的觉得，未来会怎么样，除了取决于你，还与你朝夕相处的人有关，小耿今年都大三了，回头看看这两年的大学，其实最庆幸的还是有这帮室友，也不知道怎么形容，但就是真的很好，晚上会口嗨，白天会努力，一起努力一起奋斗的室友，很多人会觉得这个不是卷吗，但我不是很明白，不都是为了自己想要的而努力，怎么会加上卷字呢，这个字在我这很不讨好。挺感谢这些个室友，万般思绪不知道怎么表达。”——努力成为程序员的耿耿（2021/10/25）

题目

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。---------蓝桥真题（Python）
思考： 字符串和子串第一个眼想到的是KMP算法，学过数据结构应该都知道，这是个子串匹配中减少回溯的算法。但显然不是，看这题子串就是从长度为1到长度为字符串长度所以这个地方可以循环，再看子串长度的开始位置与长度的关系看下图：
所以可以利用这两点在循环内部进行子串的筛选。

def count_substring(string):
    list=[] #存放子串
    for i in range(len(string)):
        j=0 #子串的第一个位置
        while(j+i<=len(string)):
            if string[j:j+i] not in list:  #字符串截取特别方便
                list.append(string[j:j+i])
            j+=1
    return len(list)#Python的方便之处

从题目难度上看在蓝桥中是送分题，就是在理解上，重点是掌握Python字符串列表的一些自带函数就能做，但是如果用c语言写的话可能会复杂一些，不过思路不变。