文档章节

poj-2752(拓展kmp)

o
 osc_1ee7cxmx
发布于 2018/08/06 16:49
字数 171
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意:求一个串所有的前后缀字串;

解题思路:kmp和拓展kmp都行,个人感觉拓展kmp更裸一点;

拓展kmp:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 500500
using namespace std;
char t[maxn];
char s[maxn];
int exnext[maxn];
int extend[maxn];
int tlen,slen;
map<int,int>m;
void get_next()
{
    int i=0,j,po;
    exnext[0]=tlen;
    while(t[i]==t[i+1]&&i+1<tlen)
        i++;
    exnext[1]=i;
    po=1;
    for(i=2;i<tlen;i++)
    {
        if(exnext[i-po]+i<exnext[po]+po)
            exnext[i]=exnext[i-po];
        else
        {
            j=exnext[po]+po-i;
            if(j<0)
                j=0;
            while(i+j<tlen&&t[j]==t[j+i])
                j++;
            exnext[i]=j;
            po=i;
        }
    }
}
int main()
{
    while(cin>>t)
    {
        tlen=strlen(t);
        get_next();
        for(int i=tlen-1;i>=0;i--)
        {
            if(exnext[i]==tlen-i)
                cout<<tlen-i<<" ";
        }
        cout<<endl;
    }
}

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Linux系统检查用户账户到期时间

如果你在 Linux 上启用了密码策略。密码必须在到期前进行更改,并且登录到系统时会收到通知。如果你很少使用自己的帐户,那么可能由于密码过期而被锁定。在许多情况下,这可能会在无需密码登...

老孟的Linux私房菜
36分钟前
13
0
关于南京哪里有开餐饮费发票?

关于南京哪里有开餐饮费发票?聚焦餐饮行业,谈话〖18 7一電一7 5 3 8一徴一3331〗研究院昨发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元.随着餐饮行业的快速...

点击fojewio
今天
7
0
android studio 4.0 打开DDMS

1、先找到AndroidStudio配置的SDK路径; 2、在SDK的/tools/路径下有个monitor.bat 的批处理文件; 3、鼠标连续点击两下monitor.bat这个批处理文件,在屏幕上会打开一个类似CMD的命令行中输入...

chenhongjiang
今天
10
0
如何在Android中使用SharedPreferences来存储,获取和编辑值

问题: Closed . 已关闭 。 This question needs to be more focused. 这个问题需要更加集中。 It is not currently accepting answers. 它当前不接受答案。 Learn more . 了解更多 。 Want...

fyin1314
今天
6
0
【JDK1.8】LinkedList源码分析

LinkedList的特性 LinkedList内部使用双向链表作为存储结构,LinkedList可以理解为链表的扩展对象,封装了常用的和非常用的操作链表的方法。以及在通过索引获取元素时的简单优化,通常Linke...

XuePeng77
今天
36
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部