526互联

day9| 28. 实现strStr()；459. 重复的子字符串

发布时间 2023-04-01 02:03:20作者: blueCP1999

28. 实现strStr()

 

题目简述：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

 

思路：

1. 暴力求解

2. 从needle的第一个字符开始，在haystack中找与之相同的字符的位置，假设在位置i。找到了，依次比较下去，也即看看needle的第二个字符与haystack的第i+1个字符是否相等。

3. 如果needle比较完了，都相等，那么返回i；否则neddle又得从第0位开始比较，haystack从第i+1位开始比较

4. 在此期间，如果haystack剩余字符长度小于neddle的长度，直接返回-1

 

代码如下：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        n1=len(haystack)
        n2=len(needle)

        if n1<n2:return -1
        if n1==n2 and haystack != needle:return -1

        ptr1=0
        ptr2=0
        while(ptr2 != n2):
            if needle[ptr2]==haystack[ptr1]:
                if n1-ptr1<n2-ptr2:
                    return -1
                else:
                    ptr2+=1
                    ptr1+=1
            elif needle[ptr2]!=haystack[ptr1]:
                ptr1=ptr1-ptr2+1
                if n1-ptr1<n2:
                    return -1 
                else:
                    ptr2=0
        return ptr1-ptr2

 

KMP算法求解：

在我暴力求解过程中，一旦发现匹配不成功，我又是从neddle的第0位开始比较，这样可能会增加代码的复杂度。

 

KMP可以解决这一问题，使得匹配失败后可以不从第0位开始，但是需要算出一个next数组，这个数组包含着needle这个字符串的构成信息，从而为我们回溯减少了一定的复杂度。

 

当匹配失败时，假如neddle的第j个字符（j从1开始）匹配失败，那我们去第j-1个字符对应的next数组的值，假如对应的值为2，我们就回到下标为2的位置，继续进行匹配比较。

这里假设haystack字符串为aabaabaafa，needle字符串为aabaaf，先给出needle对应的next数组，后文解释如何得出next数组

 

haystack: aabaabaafa

needle:    aabaaf

next:        010120

 

用下划线表示正在比较的字符，动图目前还不会画，改天改进以下补上。

 

haystack: aabaabaafa

needle:    aabaaf

next:        010120

 

相等，比较下一个字符

 

haystack: aabaabaafa

needle:    aabaaf

next:        010120

 

相等，比较下一个字符

 

haystack: aabaabaafa

 

needle:    aabaaf

 

next:        010120

 

......

 

比较至第6个字符

haystack: aabaabaafa

needle:    aabaaf

next:        010120

 

不相等，取f的前一个字符对应的next值，发现是2，于是回退到下标为2的字符开始比较

haystack: aabaabaafa

needle:          aabaaf

next:              010120

 

继续比较，可以得出结果返回

 

 

那么next里的值究竟是什么呢，怎么求呢？

 

根据KMP算法，取一个字符串的前i位，把从第0位到第k位的子串看成前缀字符串，k小于i；把从第p位到第i位的子串看成后缀字符串；如果满足两个字串相等，并且长度最大，那么next[i]里面存的就是这个长度最大值。

 

比如说 aabaaf

取a，则由于子串要小于原来的字符串，子串大小为0，于是next[0]=0

取aa，则next[1]=1，前缀取a，后缀取a

取aab，next[2]=0，后缀怎么都有b，前后缀一定不等或者只在长度为0的时候相等

取aaba，next[3]=1，前缀取a，后缀取a

取aabaa，next[4]=2，前缀取aa，后缀取aa

取aabaaf，next[5]=0，后缀怎么都有f，前后缀一定不等或者只在长度为0的时候相等

 

那么如果用代码实现呢？

 

思路如下：

1. 用指针k和指针i分别指向前缀和后缀的最后一个字符，k初始值为0，i初始值为1

2. 前缀和后缀的长度都是从1开始，如果k指向的字符和i指向的字符相等，那么k加1，next[i]等于k

3. 如果k大于0，k指向的字符和ptr2指向的字符不相等，k回退到next[k-1]

 

总的代码如下：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a=len(needle)
        b=len(haystack)
        if a==0:
            return 0
        next=self.getnext(a,needle)
        p=-1
        for j in range(b):
            while p>=0 and needle[p+1]!=haystack[j]:
                p=next[p]-1
            if needle[p+1]==haystack[j]:
                p+=1
            if p==a-1:
                return j-a+1
        return -1

    def getnext(self,a,needle):
        next=['' for i in range(a)]
        k=0
        next[0]=k
        for i in range(1,len(needle)):
            while(k>0 and needle[k]!=needle[i]):
                k=next[k-1]
            if needle[k]==needle[i]:
                k+=1
            next[i]=k
        return next

 

459. 重复的子字符串

 

题目简述：

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

 

思路：

1. 利用kmp算法，判断s是不是s+s的子串

2. 如果s是s+s的子串，并且s在t=s+s中的起始位置不为0或n，那么s就满足题目的要求

 

代码如下：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        def kmp(query: str, pattern: str) -> bool:
            n, m = len(query), len(pattern)
            fail = [-1] * m
            for i in range(1, m):
                j = fail[i - 1]
                while j != -1 and pattern[j + 1] != pattern[i]:
                    j = fail[j]
                if pattern[j + 1] == pattern[i]:
                    fail[i] = j + 1
            match = -1
　　　　　　　
　　　　　　　# 不考虑首位和末位，避免t=s+s中的起始位置为0或n
            for i in range(1, n - 1):
                while match != -1 and pattern[match + 1] != query[i]:
                    match = fail[match]
                if pattern[match + 1] == query[i]:
                    match += 1
                    if match == m - 1:
                        return True
            return False
        
        return kmp(s + s, s)

 

总结：

1. kmp算法中的next含义还需要多多理解

2. next的代码还需要多多研读理解