KMP-小学期考核

电玩女神 2022-09-25 14:20 161阅读 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 条评论，161人围观）

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

相关阅读

相关小明的字符串(kmp)

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

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

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

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

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

相关 KMP-小学期考核

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

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

相关计算机教师考核方案,教师校园网使用考核方案范文

教师校园网使用考核方案范文为了使全体教师更加熟练的掌握计算机基本知识和操作系统，充分利用校园网络进行辅助教学，提高校园网的使用效率，特制定本方案。 ![ee623e3ef

柔光的暖阳◎/ 2022年08月31日 14:17/ 0 赞/ 195 阅读

相关 kmp

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

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

相关新学期开始！

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

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

相关 2019上学期总结

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

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

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

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

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

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

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

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

相关秋季学期总结

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

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