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)


相关推荐

  • 【《重构 改善既有代码的设计》学习笔记6】重新组织函数

    本篇文章的内容来自《重构 改善既有代码的设计》一书学习笔记整理并且加上自己的浅显的思考总结!重构手法中,很大一部分是对函数进行整理,使之更恰当地包装代码。重新组织函数对过长的函数进行拆解,提炼函数,并处理局部变量,使得拆解后的函数更加清晰并且能够更好的工作。1、提炼函数(Extract Method)概要你有一段代码可以被组织在一起并独立起来。 将这段代码放进一个独立函数中,并让函…

  • 数据不平衡之SMOTE算法

    数据不平衡之SMOTE算法在企业的数据分析中,很少会遇到正负样本数据比例平衡的状况。通常情况是,绝大多数为正样本,而只有极少数(几个或者十几个)负样本。在这种情况下,不论是用LR,SVM或者基于提升方法的随机森林,直接用该数据集进行学习的效果都不会太好,原因是这些方法的学习结果都会偏向于样本较多的一类。另一个方面,对学习结果进行评估时,假如正样本占95%,负样本仅占5%,这样甚至不需要学习,直接把所有新样本预测为正,准确率

  • linux显示所有文件的大小,显示文件夹下文件的个数,hadoop命令中查看文件夹下的个数命令,模糊查询

    linux显示所有文件的大小,显示文件夹下文件的个数,hadoop命令中查看文件夹下的个数命令,模糊查询

  • Keras中创建LSTM模型的步骤[通俗易懂]

    Keras中创建LSTM模型的步骤[通俗易懂]目录写在前面概述环境1、定义网络2、编译网络3、训练网络4、评估网络5、进行预测一个LSTM示例总结写在前面本文是对The5StepLife-CycleforLongShort-TermMemoryModelsinKeras的翻译,新手博主,边学边记,以便后续温习,或者对他人有所帮助概述深度学习神经网络在Python中很容易使用Keras创建和评估,但您必须遵循严格的模型生命周期。在这篇文章中,您将了解创建、训练和评估Keras中长期记忆(LSTM)循环神经网络的分步生

  • c#键盘钩子全解

    c#键盘钩子全解usingSystem;usingSystem.Collections.Generic;usingSystem.Text;usingSystem.Runtime.InteropServices;//调用操作系统动态链接库usingSystem.Reflection;usingSystem.Diagnostics;usingMicrosoft.Win32;usingSys

  • jq正则表达式_JAVA 正则表达式

    jq正则表达式_JAVA 正则表达式一、JavaScript正则表达式正则表达式(英语:RegularExpression,在代码中常简写为regex、regexp或RE)使用单个字符串来描述、匹配一系列符合某个句法规则的字符串搜索模式。搜索模式可用于文本搜索和文本替换。什么是正则表达式?正则表达式是由一个字符序列形成的搜索模式。当你在文本中搜索数据时,你可以用搜索模式来描述你要查询的内容。正则表达式可以是一个简单的字符,或一个更…

发表回复

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

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