Codeforces 432 D. Prefixes and Suffixes

Codeforces 432 D. Prefixes and Suffixes

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

随着扩展KMP做一个简单的努力…..

D. Prefixes and Suffixes
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a string s = s1s2s|s|, where |s| is the length of string s, and si its i-th character.

Let’s introduce several definitions:

  • A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1sj.
  • The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].
  • The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|].

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input

The single line contains a sequence of characters s1s2s|s| (1 ≤ |s| ≤ 105) — string s. The string only consists of uppercase English letters.

Output

In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substringci times. Print pairs li ci in the order of increasing li.

Sample test(s)
input
ABACABA

output
3
1 4
3 2
7 1

input
AAA

output
3
1 3
2 2
3 1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=100100;

char T[maxn],P[maxn];
int next[maxn],ex[maxn];

void pre_exkmp(char P[])
{
    int m=strlen(P);
    next[0]=m;
    int j=0,k=1;
    while(j+1<m&&P[j]==P[j+1]) j++;
    next[1]=j;
    for(int i=2;i<m;i++)
    {
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) next[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<m&&P[i+j]==P[j]) j++;
            next[i]=j; k=i;
        }
    }
}

void exkmp(char P[],char T[])
{
    int m=strlen(P),n=strlen(T);
    pre_exkmp(P);
    int j=0,k=0;
    while(j<n&&j<m&&P[j]==T[j]) j++;
    ex[0]=j;
    for(int i=1;i<n;i++)
    {
        int p=ex[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) ex[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&T[i+j]==P[j]) j++;
            ex[i]=j; k=i;
        }
    }
}

int pos[maxn],sum[maxn],mx=-1;

struct ANS
{
    int a,b;
}ans[maxn];
int na=0;

bool cmp(ANS x,ANS y)
{
    if(x.a!=y.a)return x.a<y.a;
    return x.b<y.b;
}

int lisan[maxn],nl;

int main()
{
    cin>>P;
    pre_exkmp(P);
    int n=strlen(P);
    for(int i=0;i<n;i++)
    {
        pos[next[i]]++;
        lisan[nl++]=next[i];
        mx=max(mx,next[i]);
    }
    sort(lisan,lisan+nl);
    int t=unique(lisan,lisan+nl)-lisan;
    for(int i=t-1;i>=0;i--)
    {
        sum[lisan[i]]=sum[lisan[i+1]]+pos[lisan[i]];
    }
    for(int i=0;i<n;i++)
    {
        if(next[i]==n-i)
        {
            ans[na++]=(ANS){next[i],sum[next[i]]};
        }
    }
    sort(ans,ans+na,cmp);
    printf("%d\n",na);
    for(int i=0;i<na;i++)
    {
        printf("%d %d\n",ans[i].a,ans[i].b);
    }
    return 0;
}

版权声明:来自: 代码代码猿猿AC路 http://blog.csdn.net/ck_boss

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116863.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • adb命令 利用jks文件给apk签名[通俗易懂]

    adb命令 利用jks文件给apk签名[通俗易懂]程序猿日常实践是检验真理的唯一标准。jarsigner-verbose-keystorexxx.jks-signedjarxxx.apk(签名后的apk名字)xxx.apk(需要签名的apk)xxx(keystore别名)

  • emwin仪表控件_仪表开发工程师

    emwin仪表控件_仪表开发工程师本文导读i.MXRT1052具有增强型显示接口(eLCDIF),支持8/16/18/24位的数据总线模式。M1052核心板最高可支持1366×768的高清图像显示,芯片内置音频接口,搭载免费的emWin图形库可广泛应用多媒体设计。一、emWin介绍emWin是Segger公司针对嵌入式平台开发的稳定、高效的图形软件库,适合用于任何图形LCD的操作应用,并可输出高质量的无锯齿的文字和图形,通过调用…

    2022年10月14日
  • wxPython树控件

    wxPython树控件

    2021年11月22日
  • c盘扩展卷灰色无法操作的解决办法_win10c盘扩展卷是灰色的

    c盘扩展卷灰色无法操作的解决办法_win10c盘扩展卷是灰色的今天有百事网网友“丅亿页”遇到了这样一个问题:电脑C盘剩余容量太小,在看到百事网的一篇“如何合并磁盘分区windows7调整分区大小方法”文章后,也想将自己C盘系统盘空间扩大。按照上面文章中介绍的步

  • visual studio code适合什么语言_将当前运行的配置备份成初始配置

    visual studio code适合什么语言_将当前运行的配置备份成初始配置VSCode是一款非常好用的编辑器(或者IDE),具有很好的可扩展性,功能比较强大,占用的系统资源也适中,启动速度较快,而且支持全平台,比较适合作为Python开发用的IDE。本文针对Linux(主要是Ubuntu,其他发行版类似),整合一些Python开发相关的配置,仅供刚入坑Linuxer参考。一、VSCode与其他编辑器(或IDE)的比较(1)VSCode与Atom的比较:Atom是一款由g…

  • zabbix监控网络设备

    zabbix监控网络设备终工作中遇到,办公网有防火墙和交换机,要监控一下他们的流量。可以通过zabbix来做。从整个操作过程来看,主要有两个难点。监控的原理是,zabbix模板里用自带的OID,去交换机上获得值,因此,我们要开启交换机上的snmp,另外要拿到相关监控项的OID值。再去zabbix上添加监控模板就可以了。开启交换机的snmp功能这里不做介绍,因为不是我开的,所以这部分以后补充。下面先介绍如何获得…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号