leetcode 459 重复的子字符串

简介: leetcode 459 重复的子字符串

重复的子字符串


7fdda62e7e2142eb816efd85e7b6da4f.png

提取小串做模式组,再进行KMP匹配

(复杂度高)

class Solution {
public:
    void getNext(int* next, const string& s)
    {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++)
        {
            while (j >= 0 && s[i] != s[j + 1])
            {
                j = next[j ];
            }
            if (s[i] == s[j + 1]) j++;
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        string substr;
        if(s.size()==0) return false;
        for (int cur = 0; cur < s.size(); cur++)//循环找小串
        {
            if (s[cur] != substr[0]) substr += s[cur]; //文字串中和小串第一个不相同的加入小串
            else //发现文字串有和小串开头相同的
            {
                int *next = new int[substr.size()];
                getNext(next, substr);
                int j = -1;
                for (int i = 0; i < s.size(); i++) //kmp
                {
                    if (  s[i] != substr[j + 1])//发现有匹配失败的,直接跳出给小串加长
                    {
                        j = next[j ];//应该是没啥用,从kmp复制过来的。这个题不涉及退回,发现错误直接跳出了
                        break;
                    }
                    if (s[i] == substr[j + 1])
                    {
                        j++;
                    }
                    if (i == (s.size() - 1) && j == (substr.size() - 1)) //发现匹配成功,并且匹配的成功最后一个就是整个文字串的最后一个。返回成功
                    {
                        return true;
                    }
                    if (j == substr.size() - 1)
                    {
                        j = -1;
                    }  
                }
                delete[] next;
                substr += s[cur];
            }
        }
        return false;
    }
};


直接KMP算法

aec6cf5484f74513b878eb467c583fa0.png

class Solution {
public:
    void getNext(int* next, const string& s)
    {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++)
        {
            while (j >= 0 && s[i] != s[j + 1])
            {
                j = next[j ];
            }
            if (s[i] == s[j + 1]) j++;
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
       if (s.size() == 0) {
            return false;
        }
        int *next = new int[substr.size()];
        //计算整个文字串的next数组,如果文字串是循环的,一个循环next都是-1,之后的从0开始递增。next的最后一位的值=(循环次数-1)*循环体长度 -1
        getNext(next, s);
        int len = s.size();
        //文字串的长度减去next数组最后一位+1 ,得到是循环体长度
        // 如果next数组最后一位不是-1(意味着之前匹配成功) , 并且文字串长度对循环体长度可以整除
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) 
        {
            delete[] next;
            return true;
        }
        delete[] next;
        return false;
    }
};

二刷

移动匹配法

e9ecb2d40470483fbeda89aeedd9cfce.png

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string tmp = s + s;
        tmp.erase(0,1);
        tmp.erase(tmp.size()-1,1);
        if(tmp.find(s) == -1) return false;
        else return true;
    }
};

KMP

class Solution {
public:
    void getnext(int *next , const string &s)
    {
        int j=-1;
        next[0] = j;
        for(int i=0 ; i<s.size() ;i++)
        {
            while(j>=0 && s[i] != s[j+1])
                j = next[j];
            if(s[i] == s[j+1])
                j++;
            next[i] = j;
        }
        return ;
    }
    bool repeatedSubstringPattern(string s) {
        int j=-1;
        int next[s.size()];
        getnext(next ,s);
        if(next[s.size()-1] != -1  &&  s.size() % ( s.size() -  ( next[s.size()-1] -1 )  )  ==0 )
            return true;
        else
            return false;
    }
};


相关文章
|
1天前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
2天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
6天前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
6天前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
6天前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
6天前
|
存储 算法 数据挖掘
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
|
6天前
|
存储 SQL 算法
LeetCode题目43:字符串相乘
LeetCode题目43:字符串相乘
|
6天前
|
SQL 算法 数据可视化
LeetCode第八题:字符串转换整数 (atoi)【8/1000 python】
LeetCode第八题:字符串转换整数 (atoi)【8/1000 python】
|
10天前
|
算法 Java Go
【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)
6 0