51nod 1304 字符串的相似度（exkmp）

朱雀 2021-12-24 09:05 136阅读 0赞

拓展kmp裸题

自己跟自己匹配即可

模板测试=v=

#include <iostream>
    #include <cstring>
    using namespace std;
    const int maxn = 1e6 + 100;
    char S[maxn];
    int Next[maxn], extend[maxn];
    void GetNext(char *T, int *Next){
        int len = strlen(T);
        Next[0] = len;
        int a, p;
        for(int i = 1, j = -1; i < len; i++, j--){
           if(j < 0 || i + Next[i-a] >= p){
                if(j < 0) p = i, j = 0;
                while(p < len && T[p] == T[j])
                    p++, j++;
                Next[i] = j;
                a = i;
           } else Next[i] = Next[i-a];
        }
    }
    void GetExtend(char *S, char *T, int *extend, int *Next){
        GetNext(T, Next);
        int a, p;
        int slen = strlen(S), tlen = strlen(T);
        for(int i = 0, j = -1; i < slen; i++, j--){
            if(j < 0 || i + Next[i-a] >= p){
                if(j < 0) p = i, j = 0;
                while(p < slen && j < tlen && S[p] == T[j]) p++, j++;
                extend[i] = j;
                a = i;
            } else extend[i] = Next[i-a];
        }
    }
    
    int main()
    {   
        cin>>S;
        int len = strlen(S);
        GetNext(S, Next);
        long long ans = 0;
        for(int i = 0; i < len; i++)  ans += Next[i];
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Saurus/p/7637534.html

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1347 旋转字符串

[1347 旋转字符串][1347] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [1347]: http://www.51n

灰太狼/ 2024年02月17日 22:55/ 0 赞/ 6 阅读

相关 51nod1304 字符串的相似度(扩展kmp)

[1304 字符串的相似度][1304] ![ok.png][] 题目来源： [1304]: http://www.51nod.com/onlineJudge/quest

雨点打透心脏的1/2处/ 2024年02月17日 22:19/ 0 赞/ 9 阅读

相关 python比较两个字符串相似度,【Python】比较字符串相似度

字符串相似度应用场景：拼写纠错、文本去重、上下文相似性、不同来源数据对比等。评价字符串相似度最常见的办法就是：把一个字符串通过插入、删除或替换这样的编辑操作，变成另外一个字

ゝ一世哀愁。/ 2023年01月17日 04:55/ 0 赞/ 221 阅读

相关 php 两个字符串相似度,比较两个字符串的相似度

比较两个字符串的相似度public class Levenshtein \{ private int compare(String str, String target) \

太过爱你忘了你带给我的痛/ 2023年01月13日 04:02/ 0 赞/ 190 阅读

相关 html 字符串相似度,fuzzywuzzy：计算两个字符串之间的相似度

楔子 fuzzywuzzy是用来计算两个字符串之间的相似度的，它是依据Levenshtein Distance算法来进行计算的 Levenshtein Distance 算

女爷i/ 2022年10月11日 03:54/ 0 赞/ 239 阅读

相关计算字符串相似度及寻找最相似字符串的代码

计算两个字符串的差异距离函数 /// <summary> /// 计算两个字符串的差异距离 /// </summary> /// <param

灰太狼/ 2022年10月02日 15:56/ 0 赞/ 244 阅读

相关字符串相似度计算

对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为： 1.修改一个字符（如把“a”替换为“b”）;　　

冷不防/ 2022年08月06日 00:27/ 0 赞/ 224 阅读

相关计算字符串的相似度

转自：[http://www.cnblogs.com/yujunyong/articles/2004724.html][http_www.cnblogs.com_yujunyo

川长思鸟来/ 2022年05月24日 12:10/ 0 赞/ 290 阅读

相关计算字符串的相似度

1.百度百科介绍： Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一

旧城等待，/ 2022年03月20日 10:14/ 0 赞/ 301 阅读

相关 51nod 1304 字符串的相似度（exkmp）

拓展kmp裸题自己跟自己匹配即可模板测试=v= include <iostream> include <cstring> using name

朱雀/ 2021年12月24日 09:05/ 0 赞/ 137 阅读