重复的子字符串（K M P算法)

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

class Solution {
public:
    void next_array(string s,int *next)
    {   next[0]=0;
        int j=0;
        for(int i=1;i<s.size();i++)
        {
            while(j>0&&s[i]!=s[j])
            {
                j=next[j-1];//j就是数组元素的值，回退就按数组元素形式回退。
            }
            if(s[i]==s[j])
            {
                j++;//j++就代表着最长相等前后缀的个数的迭代
            }
            next[i]=j;  //j就是数组元素的值，
        }
    }
 
    bool repeatedSubstringPattern(string s) {
        int len=s.size();
        int next[len];
        next_array(s,next);
        if(next[len-1]!=0&&(len%(len-next[len-1])==0))//这里的取余等式是根据推导得出
        //ababab
        //001234  最小子串=len-4
        {
                return true;
        }
        return false;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

strSTR（）的实现

28. 实现 strStr()
    实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

class Solution {
public:
    void next_arr(string neddle,int *next)
    {
        next[0] = 0;
        int j = 0;
        for(int i = 1;i<neddle.size();i++)
        {
            while(j>0 && neddle[i] != neddle[j])
            {
                j = next[j-1];
            }
            if(neddle[i] == neddle[j])
            {
                j++;

            }   
            next[i] = j;
        }

    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int len = needle.size();
       // vectornext(len,0); 这里用容器也可以
        int next[needle.size()];
        next_arr(needle,next);
        int j = 0;
        for(int i = 0;i<haystack.size();i++)
        {
            while(j > 0&&haystack[i] != needle[j])
            {
                j = next[j - 1]; //j就是数组元素的值，回退就按数组元素形式回退。
            }//此循环不能放if后面 ，因为j++对while循环有影响。
            if(haystack[i] == needle[j])
            {
                j++;
             }
                    if(j >= needle.size())
                {
                    return (i - needle.size() + 1);
                }
             
           

        }

    return -1;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53