-1

我知道在 python 中有一个in运算符可以用来检查字符串中是否存在任何子字符串或字符。我想通过检查每个字符串（长度子字符串）来做到这一点。下面的代码是唯一的方法还是有其他方法可以实现这一目标？

m = "college"
s = "col"
lm = len(m)
ls = len(s)
f = 0

for i in range(lm):    
    if (i+ls) <= lm:
        if s == m[i:(i+ls)]:            
            global f
            f = 1
            break
if f:
    print "present"
else:
    print "not present"

我在这里所做的是，如果我的子字符串是col，我的程序通过从主字符串的开头到结尾移动来检查长度子字符串和子字符串的字符串，并返回 true 与否。

col
oll
lle
leg
ege
4

4 回答 4

2

您的代码是快速实现一般子字符串搜索的合法方式，但不是唯一的方式。更有效的算法包括Boyer-Moore 字符串搜索、Knuth-Morris-Pratt 搜索或使用DFA实现的搜索。

这是一个很大的话题，您的问题并没有说明您实际需要什么样的信息。在 Python 的情况下，简单地使用in运算符和相关方法当然是最有效str.find的str.index，所有这些都部署了一个简化的 Boyer-Moore。

于 2013-05-11T19:17:26.850 回答
1

你可以尝试这样的事情：

In [1]: m = 'college'

In [2]: s = 'col'

In [3]: if any(m[i:i+len(s)] == s for i in range(len(m)-len(s)+1)):
   ...:     print 'Present'
   ...: else:
   ...:     print 'Not present'
   ...:     
Present

检查any每个m长度的子串len(s)并查看它是否等于s. 如果是这样，它会返回True并停止进一步的处理（这称为“短路”，与break您上面的非常相似）。

any如果我们用列表推导替换它并取出相等比较，这就是该部分的样子：

In [4]: [m[i:i+len(s)] for i in range(len(m)-len(s)+1)]
Out[4]: ['col', 'oll', 'lle', 'leg', 'ege']
于 2013-05-11T19:11:41.323 回答
1

你不需要global那里。另外，你可以做

In [1]: %paste
m = "college"
s = "col"

In [2]: 'not ' * all(s != m[i:i+len(s)] for i in range(1+len(m)-len(s))) + 'present'
Out[2]: 'present'

但实际上你当然应该这样做s in m，

于 2013-05-11T19:13:07.253 回答
0

这类问题需要功能性解决方案：

def strcomp(s, subs):
    if len(s) < len(subs):
        return False
    elif s[0:len(subs)] == subs:
         return True
    else:
        return strcomp(s[1:], subs)

您递归调用该strcomp函数，每次都使用“长”字符串 -s失去它的头部，直到您找到subs第一个位置或s变得比subs.

于 2013-05-11T19:22:39.447 回答