CF 246 div2 D Prefixes and Suffixes (所有前缀的出现次数)

系统管理员 2022-08-23 13:52 17阅读 0赞

题目链接：http://codeforces.com/contest/432/problem/D

题意：对一个长度不超过10^5的字符串，按长度输出和后缀完全匹配的的前缀的长度，及该前缀在整个串中出现的次数。（可重叠）

#include <cstdio>
    #include <cstring>
    
    const int N=100005;
    
    char str[N];
    int next[N],cnt[N],ansp[N],ansn[N],n;
    
    void getNext (char s[],int len)
    {
        next[0]=-1;
        int i=0,j=-1;
        while (i<len)
        {
            if (j==-1 || s[i]==s[j])
                next[++i]=++j;
            else j=next[j];
        }
    }
    
    void KMP ()
    {
        int i=0,j=0;
        while (i<n)
            if (j == -1 || str[i] == str[j])
                i++,j++,cnt[j]++;
            else
                j=next[j];
    
        for (i=n;i>0;i--) //统计每个前缀出现次数,cnt[i]表示长度为i的前缀出现了cnt[i]次
            if (next[i] != -1)
                cnt[next[i]] += cnt[i];
    }
    
    int main ()
    {
        scanf("%s",str);
        n=strlen(str);
        memset(cnt,0,sizeof(cnt));
        getNext(str,n);
        KMP();
    	int t=n,sum=0;
        while (t) //前缀匹配后缀
        {
            ansp[sum]=t;
            ansn[sum++]=cnt[t];   //
            t=next[t];
        }
        printf("%d\n",sum);
        for (int i=sum-1;i>=0;i--)
            printf("%d %d\n",ansp[i],ansn[i]);
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 CF862 div2 D. A Wide, Wide Graph

[Problems - Codeforces][] ![d54b2f1d55aa48239a91dc1fcb026829.png][] 思路：因为要我们输出k为1~n的

╰+攻爆jí腚メ/ 2024年03月24日 14:04/ 0 赞/ 61 阅读

相关【MST+GCD】CF714div2 D. GCD and MST

第一次写2000分的题，把大致思路想出来了但是差点细节比如vis数组没加，区间贡献算错了对于这些，思路对的但是差点细节的题，应该多模拟样例，不然写出来会很抽象 [

朱雀/ 2024年03月22日 13:13/ 0 赞/ 59 阅读

相关【贪心（计算贡献）+操作】CF833div2 C. Zero-Sum Prefixes

这道题考虑贪心，计算贡献就好了 [Problem - C - Codeforces][] 题意：定义一个数列的值为前缀和为0的位置个数，每次操作可以把一个ai==0的数

àì夳堔傛蜴生んèń/ 2024年03月22日 06:06/ 0 赞/ 56 阅读

相关 CF 246 div2 D Prefixes and Suffixes (所有前缀的出现次数)

题目链接：http://codeforces.com/contest/432/problem/D 题意：对一个长度不超过10^5的字符串，按长度输出和后缀完全匹配的的前缀的长

系统管理员/ 2022年08月23日 13:52/ 0 赞/ 18 阅读

相关 leetcode 745. Prefix and Suffix Search 字典树（前缀树）

Given many words, words\[i\] has weight i. Design a class WordFilter that supports one

傷城~/ 2022年06月03日 09:56/ 0 赞/ 189 阅读

相关 Codeforces1092C. Prefixes and Suffixes——————思维，字符串

C. Prefixes and Suffixes Ivan wants to play a game with you. He picked some string s

àì夳堔傛蜴生んèń/ 2022年04月03日 09:54/ 0 赞/ 202 阅读

相关 CODEFORCE 246 Div.2 B题

题目例如以下： B. Football Kit time limit per test 1 second memory limit per test 256 mega

Love The Way You Lie/ 2022年03月31日 08:36/ 0 赞/ 194 阅读

相关 Codeforces Round #294 (Div. 2) D. A and B and Interesting Substrings [dp 前缀和 ]

[传送门][Link 1] D. A and B and Interesting Substrings time limit per test 2 seconds me

骑猪看日落/ 2021年12月23日 10:27/ 0 赞/ 187 阅读

相关 D. Prefixes and Suffixes（KMP+dp）

参考博客：[https://blog.csdn.net/huanghongxun/article/details/53209004][https_blog.csdn.net_h

- 日理万妓/ 2021年11月05日 13:48/ 0 赞/ 246 阅读

相关 SpringMVC--视图解析器概述和前缀prefix、后缀suffix

Spring MVC视图解析器配置 Spring 视图解析器是 Spring MVC 中的重要组成部分，用户可以在配置文件中定义 Spring MVC 的一个视图解析器（

待我称王封你为后i/ 2021年08月13日 13:16/ 0 赞/ 437 阅读