算法练习-day8

字符串

28. 找出字符串中第一个匹配项的下标

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

示例：

       思路：本题有两种思路：1.暴力求解法，只需要一次遍历，以i为haystack字符串的起始，对needle的第一个元素进行对比，若相等则继续循环对比，当出现比较元素次数等于needle字符串长度时，就说明i开头就是needle字符串第一次出现的位置，时间复杂程度为O(m*n)；2.KMP算法求解，我们使用KMP算法，可以跳过一些不必要的比较，比如：haystack=“aaaaaaaab”，needle=“aab”，此时我们就需要多次重复比较aa，直到最后匹配成功，这是非常麻烦的，而我们使用KMP算法，最直观的就是指向needle的指针不用回退，就算不动也不会从0开始比较，这也是KMP算法的优点；其次是next数组的建立，该数组就是匹配比较失败后，哪个haystack数组中元素该和needle数组元素进行比较

这里我建议大家可以看下这个视频，对KMP算法的了解会更加透彻：KPM算法

方法1代码：

    int strStr(string haystack, string needle) {
        for (int i = 0; i<haystack.size(); i++)
        {
            int j = 0;
            if (haystack[i] == needle[j])
            {
                int n = i;
                while (j < needle.size() && haystack[n] == needle[j])
                {
                    n++, j++;
                }
                if (n - i == needle.size())
                {
                    return i;
                }
            }
        }
        return -1;
    }

方法2代码：

    vector<int> BuildNext(string& needle)//创建next数组
    {
        vector<int> next;
        int i = 1, prefix = 0;//i表示走到的数组位置，prefix表示前缀长度
        next.push_back(0);//第一个元素的前缀长度一定为0
        while (i<needle.size())
        {
            if (needle[i] == needle[prefix])//当元素相等时，前缀长++，i继续向后移动
            {
                prefix++;
                next.push_back(prefix);
                i++;
            }
            else
            {
                if (prefix == 0)//当prefix为0时，说明该元素没有与之相等的前缀长
                {
                    next.push_back(prefix);
                    i++;
                }
                else//寻找之前前缀长
                {
                    prefix = next[prefix - 1];
                }
            }
        }
        return next;
    }
    int strStr(string haystack, string needle) {
        vector<int> next = BuildNext(needle);
        int i = 0, j = 0;
        while (i < haystack.size())
        {
            if (haystack[i] == needle[j])//当两个元素相等时，++i，++j
            {
                i++,j++;
            }
            else if (j>0)//不等时，可以跳过之前匹配的needle元素，让haystack的不匹配元素和needle的下一个待匹配元素比较
            {
                j = next[j - 1];
            }
            else
            {
                i++;
            }
            if (j == needle.size())
            {
                return i - j;
            }
        }
        return -1;
    }

459. 重复的子字符串

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

示例：

       思路：1.旋转数组法，若字符串全部由子串组成，则说明字符串是对称的，因此，我们可以将字符串一个个向后移动，在字符串遍历结束前，当移动后字符串等于移动前字符串时，就说明该字符串就是由子串组成；2.KMP算法，由于当字符串为子串组成的时，next数组会形成第一段子串为0，其他子串递增的情况，因此当我们得到next数组后，只需要判断两点：

1. next数组末尾不为0
2. 整个字符串%一组字串为0

即可说明，该字符串就是由子串组成 

方法1代码：

    bool repeatedSubstringPattern(string s) {
        for(int i=1;i<s.size();i++)
        {
            string clone=s.substr(i)+s.substr(0,i);
            if(clone==s)
            {
                return true;
            }
        }
        return false;
    }

方法2代码：

    vector<int> BuildNext(string& s)
    {
        vector<int> next;
        next.push_back(0);
        int i=1,prefix=0;
        while(i<s.size())
        {
            if(s[prefix]==s[i])
            {
                prefix++;
                next.push_back(prefix);
                i++;
            }
            else
            {
                if(prefix==0)
                {
                    next.push_back(prefix);
                    i++;
                }
                else
                {
                    prefix=next[prefix-1];
                }
            }
        }
        return next;
    }
    bool repeatedSubstringPattern(string s) {
        vector<int> next = BuildNext(s);
        int len = next.size();
        if (next[len-1] != 0 && (len % (len - next[len-1]) == 0))
        {
            return true;
        }
        return false;
    }