字符串篇11. 字符串匹配

7875

发布于未知归属地

简介

本文为字符串篇中关于字符串匹配的题解，共四题。

28. 实现 strStr()

分析

本问题要求实现字符串匹配算法。我们可以直接暴力匹配。一个效率更高的算法是kmp算法。在暴力匹配的算法中，当遇到不匹配的情况(a[i]!=b[j])时，下一次的匹配将模式串从0(b[0])开始，而主串从下一个字符(a[i-j+1])开始。而kmp算法中，遇到不匹配的情况时，模式串并不需要从0开始，我们首先预处理一个数组nxt[j]代表当j匹配失败时回退的位置。那么，nxt[j]应该为满足b[0:k]==b[j-k-1:j-1]最大的k。那么预处理nxt[j]时，相当于模式串自己与自己的子串匹配。当b[j]与b[k]不匹配时，回退到nxt[k]即可。C++字符串类中有find()函数，C语言中的strstr()函数都可以直接解决本问题。

参考代码

class Solution {
public:
    vector<int> getNext(string s) {
        vector<int> ret(s.length(), -1);
        int j = 0, k = -1;
        while (j + 1 < s.length()) {
            if (k == -1 || s[j] == s[k]) {
                k++; j++; ret[j] = k;
            } else {
                k = ret[k];
            }
        }
        return ret;
    }
    int strStr(string haystack, string needle) {
        vector<int> nxt = getNext(needle);
        if (needle.length() == 0) {
            return 0;
        }
        int i = 0, j = 0;
        while (i < haystack.length()) {
            if (j == -1 || haystack[i] == needle[j]) {
                i++; j++;
            } else {
                j = nxt[j];
            }
            if (j == needle.length()) {
                return i - j;
            }
        }
        return -1;
    }
};

686. 重复叠加字符串匹配

分析

我们首先特殊判断B是否为A与A重复叠加两次的子串，对于重复三次以上的情况，必能在B中找到A，我们找到第一次出现的位置，之后该位置之前和之后的空格都用A补齐，再判断补齐后的字符串是否和B相同，并计算一共用到多少个A。

参考代码

class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        if (A.find(B) != -1) {
            return 1;
        }
        if ((A+A).find(B) != -1) {
            return 2;
        }
        int p = B.find(A), j = 0, ret = 1;
        if (p == -1) {
            return p;
        }
        for (int i = p + A.size(); i < B.size(); i++) {
            if (B[i] != A[j]) {
                return -1;
            }
            j++;
            if (i + 1 < B.size() && j >= A.size()) {
                j = 0; ret++;
            }
        }
        if (p + A.size() < B.size()) {
            ret++;
        }
        j = A.length() - 1;
        for (int i = p - 1; i >= 0; i--) {
            if (B[i] != A[j]) {
                return -1;
            }
            j--;
            if (i > 0 && j < 0) {
                j = A.length() - 1; ret++;
            }
        }
        if (p > 0) {
            ret++;
        }
        return ret;
    }
};

459. 重复的子字符串

分析

若某个字符串可由一个子串重复多次构成，那么它循环移动若干次后和原串相同，那么我们只需要将原串重复两次，去掉头尾(不去掉头尾的话新串必定包含原串)，若新串包含原串，则说明可以由子串重复多次构成。

参考代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = (s + s).substr(1, s.length()*2-2);
        return t.find(s) != -1;
    }
};

214. 最短回文串

分析

记s的倒序为t,长度为len，我们要找的是s[0:k]与t[len-k-1:len-1]相等最大的k，这部分是以0开头最长的回文子串，不需要添加元素。回忆字符串匹配的kmp算法，其中getnext函数找的是s[0:k]与s[j-k-1:j-1]相等最大的k。所以我们将s和t连接起来。中间用分隔符隔开，之后对连接的字符串求next，next数组最后的元素+1即为我们要添加的字符数。

参考代码

class Solution {
public:
    vector<int> getNext(string s) {
        vector<int> ret(s.length(), -1);
        int j = 0, k = -1;
        while (j + 1 < s.length()) {
            if (k == -1 || s[j] == s[k]) {
                k++; j++; ret[j] = k;
            } else {
                k = ret[k];
            }
        }
        return ret;
    }
    string shortestPalindrome(string s) {
        string rev(s);
        reverse(rev.begin(), rev.end());
        string t = s + "#" + rev;
        vector<int> f = getNext(t);
        return rev.substr(0, s.size() - f.back()-1) + s;
    }
};