KMP-小学期考核

电玩女神 2022-09-25 14:20 137阅读 0赞

题目大意：给你一个数字串A，找出数字串的所以前缀B（不包括本身），求B的前缀和后缀完全匹配的最大个数所形成的数字串C，特别的因为前后缀也不包括本身，所以当只有一个数字时最大匹配为 -1 ！

题目例子： eg： A ：1 2 3 4 5   所以  B： 1     1 2    1 2 3    1 2 3 4   所以四个B的前后缀的最大匹配为 -1 0 0 0   即最后的答案为  -1 0 0 0  （题目描述还有个最小字典序，因为第一个必须为-1  后面的最下也为0  所以求出来的就是最小字典序，这是题目设的坑！）

题目思路：题目描述还是有点绕口，其实就是求A的所有前缀的前缀和后缀的最大匹配，不难发现这就是KMP的next数组，所以本题就是求数字串A的next数组，当然要去掉next数组的最后一个和第二个,当然还要特判只有一个数字的情况！

代码：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    const int maxn=200;
    int str[maxn];
    int ans[maxn];
    int Next[maxn];
    void getnext(int len)
    {
        int Max=0;
        int i=-1,j=0;
        Next[0]=-1;
        while(j<len)
        {
            if(i==-1||str[i]==str[j])
            {
                ++i,++j;
                Next[j]=i;
            }
            else
                i=Next[i];
            if(j>=2)ans[j-1]=Next[j];
        }
        ans[j-1]=Next[j-1];
        return ;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&str[i]);
            int len=n;
            ans[0]=-1;
            getnext(len);
            for(int i=0;i<n-2;i++)
                printf("%d ",ans[i]);
            printf("%d\n",ans[n-2]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关小明的字符串(kmp)

记录一道KMP的题目，这道题对于刚接触kmp的同学来说算是一道不错的题目了，能够帮助我们理解得更深刻... 题目：小明的字符串题目描述

骑猪看日落/ 2024年03月31日 13:11/ 0 赞/ 39 阅读

相关临近学期末，给大家带来8个小项目

1、C语言——小型图书管理系统 https://blog.csdn.net/HeZhiYing\_/article/details/80627622 2、C语言——抽

- 日理万妓/ 2022年12月10日 08:45/ 0 赞/ 99 阅读

相关 KMP-小学期考核

题目大意：给你一个数字串A，找出数字串的所以前缀B（不包括本身），求B的前缀和后缀完全匹配的最大个数所形成的数字串C，特别的因为前后缀也不包括本身，所以当只有一个数字时最大匹配

电玩女神/ 2022年09月25日 14:20/ 0 赞/ 138 阅读

相关 kmp

include <iostream> include <cstdio> include <string> include <cstring>

曾经终败给现在/ 2022年06月09日 07:51/ 0 赞/ 131 阅读

相关新学期开始！

今天注册、开年级会之类的事忙忙碌碌了一天，累死了...明天就是新学期了。这学期的那门《可视化程序设计》课果然是教C\的，翻了一下那本教材，似乎还不错的样子。嗯，终于

朱雀/ 2021年12月07日 15:13/ 0 赞/ 233 阅读

相关 2019上学期总结

一丶我所学的内容 ![1580711-20190622005044988-1193038223.png][] ![1580711-20190622005051937

以你之姓@/ 2021年11月27日 06:16/ 0 赞/ 260 阅读

相关个人总结——学期总结

<table style="width:481px;"> <thead> <tr> <td> <p>这个作业属于哪个课程</p> </td> <td>

￡神魔★判官ぃ/ 2021年11月14日 14:34/ 0 赞/ 425 阅读

相关分享人工智能实验室部门考核的第一份小作业

关注知乎“[Py生活][Py]”，分享工作心得和生活感悟。 -------------------- 上周已经结束了入职培训，从这周开始，我应该和大家分享技术知识，但进入了

你的名字/ 2021年10月14日 00:34/ 0 赞/ 218 阅读

相关秋季学期总结

![1580654-20190219191328785-740745651.png][] 第一次接触C语言这门课程，感觉自己就是一个小白，什么都不知道，经过一个学期后，我会动

妖狐艹你老母/ 2021年09月20日 08:40/ 0 赞/ 465 阅读

相关 kmp

如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离由匹配数组ne的含义可知 p[1..k] = p[j-k+1

红太狼/ 2021年06月22日 15:37/ 0 赞/ 338 阅读