现在的位置: 首页 > 综合 > 正文

GG的匹配串 ______(广东工业大学2015校赛初赛)

2018年05月03日 ⁄ 综合 ⁄ 共 1019字 ⁄ 字号 评论关闭

Description

2015年广东工业大学ACM校赛要来~\(≧▽≦)/~辣辣辣,作为校赛的出题人之一,GG想出了一道水题来考考大家。相信小伙伴们都学过字符串匹配,于是字符串匹配的水题就诞生辣!GG给出了一段长度为N的大写字母序列,现在他要你修改这一段字母序列,使得这段字母序列上最前面的K个字母组成的序列与最后面的K个字母组成的序列一一匹配。 
 
例如对于序列“ATUUUUAC”和K = 2,可以通过将第二个字母修改为“C”,使得最前面的两个字母与最后面的两个字母都为“AC”,当然 还存在其他的修改方法,现在GG要求你求出要使字符串匹配至少需要修改多少个字母。

Input

有T组数据输入。(T <= 100) 
每组数据只有两行,第一行为一个字符串,第二行为一个正整数K,字符串的长度不会超过1000,且至少为1。(1 <= K <= N)。

Output

对于每组数据输出至少需要修改的字母数量

Sample Input

2
ATUUUUAC
2
ATACGTCT
6

Sample Output

1
3



题意:这道题可能有的人读不懂题意,修改字符的时候可能会影响到前后俩个子串的字符,所以第二个样例数据虽然前后两个子串有4个字符不匹配,但是只需要改3次.

分析:假设 n=8,k=6;

图中用线连起来的就是要相同的.

我们发现每隔 n-k  字符都要相同,那么我们就只需要对于每个i ,下标为 i + m * (n-k) 的字符中出现次数最多的字母为 ' * ' ,那么我们就把 i + m * (n-k)这些字符全部改为 ' * ' ;

这也算是一个贪心的思想.

上代码:

#include <stdio.h>
#include <string.h>
char str[10000];
int N,n,j,k,m,a[26];
int find(int x)
{
    int c=0;
    memset(a,0,sizeof(a));
    while(x<n)
    {
        a[str[x]-'A']++;
        x=x+m;
        c++;
    }
    int max=0;
    for(int i=0;i<26;i++)
        max=(max>a[i])? max:a[i];
    return c-max;
}
int main()
{
    scanf("%d",&N);
    while(N--)
    {
        scanf("%s",str);
        scanf("%d",&k);
        n=strlen(str);
        m=n-k;
        int ans=0;
        for(int i=0;i< k && i< m;i++) 
        {
            ans+=find(i);
        }
        printf("%d\n",ans);
    }
    return 0;
}

抱歉!评论已关闭.