【算法练习】哞叫时间

一、题目

农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。

他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

埃尔茜仍然不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图解释他的意思。

竞赛被定义为一个长度为 N 的小写字母字符串。

一种哞叫一般地定义为子串 cicjcj，其中某字符 ci 之后紧跟着 2 个某字符 cj，且 ci≠cj。

根据农夫约翰的说法，贝茜哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 F 次，那可能就是贝茜发出的。

然而，农夫约翰的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。

将可能的误差考虑在内，输出所有可能是贝茜发出的哞叫，按字母顺序排序。

输入格式
输入的第一行包含 N 和 F，表示字符串的长度以及贝茜的哞叫的频次下限。

第二行包含一个长度为 N 的小写字母字符串，表示竞赛。

输出格式
输出可能是贝茜发出的哞叫的数量，以下是按字典序排序的哞叫列表。

每行输出一种哞叫。

数据范围
3≤N≤20000,1≤F≤N

输入样例1：
10 2
zzmoozzmoo
输出样例1：
1
moo
样例1解释
在这个样例中，任何字符变化都不会影响答案。
唯一贝茜可能发出的哞叫是 moo。
输入样例2：
17 2
momoobaaaaaqqqcqq
输出样例2：
3
aqq
baa
cqq
样例2解释
在这个样例中，位置 8
（从零开始索引）的 a 可能是由 b 损坏导致的，这使得 baa 成为一种贝茜发出两次的可能的哞叫。
此外，位置 11
的 q 可能是由 c 损坏导致的，这使得 cqq 成为一种贝茜可能的哞叫。
aqq 可以通过将 c 换成 a 来达到。
输入样例3：
3 1
ooo
输出样例3：
25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

二、分析

题解思路:
先算出没有修改的abb形式，在统计修改后的修改一个字符只会影响当前以及前两个字符的abb形式。

三、题解

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

using namespace std;

const int N= 20010,M = 26;
int n,m;
char s[N];
int cnt[M][M];
bool st[M][M];


void update(int r,int k,int v)
{
    r = max(0,r),k=min(k,n-1);
    for(int i = r;i+2<= k;i++)
    {
        char a = s[i],b=s[i+1],c = s[i+2];
        if(a!=b && b== c)
        {
            cnt[a][b] += v;
            if(cnt[a][b] >=m) 
            {
                st[a][b] = true;
            }
        }
        
    }
}

int main()
{
    scanf("%d%d%s",&n,&m,s);
    
    for(int i = 0;i<n;i++)
    {
        s[i] -= 'a';
    }
    
    update(0,n-1,1);
    
    for(int i = 0;i<n;i++)
    {
        char a = s[i];
        update(i-2,i+2,-1);
        for(int j =0;j<26;j++)
        {
            if(a!= j)
            {
                s[i]= j;
                update(i-2,i+2,1);
                update(i-2,i+2,-1);
            }
        }
        s[i]= a;
        update(i-2,i+2,1);
    }
    
    int res = 0;
    for(int i = 0;i<26;i++)
    {
        for(int j = 0;j<26;j++ )
        {
            if(st[i][j]) res++;
        }
        
    }
    printf("%d\n",res);
    
    for(int i = 0;i<26;i++)
    {
        for(int j= 0;j<26;j++)
        {
            if(st[i][j])
            {
                printf("%c%c%c\n",i+'a',j+'a',j+'a');
            }
        }
    }
    
    
    return 0;
    
}

总结

到这里这篇文章的内容就结束了，谢谢大家的观看，如果有好的建议可以留言喔，谢谢大家啦！