题解 | #DNA序列#

#include <stdio.h>
#include <string.h>

// 1. 获得字符串和长度
// 2. 双指针滑动窗口，相当于队列解决

int main() {
    
    char input[1010] = {0};
    int n = 0;
    gets(input);
    scanf("%d", &n);

    int head = 0;
    int rear = head + n;
    int len = strlen(input);
    //下标是起点， 值是该子串CG的个数
    int record[1000] = {0};

    for(int i = 0; i < rear; ++ i)
    {
        if(input[i] == 'C' || input[i] == 'G')
        {
            ++ record[head];
        }
    }

    //[head, rear)在队列中
    for(++ head, ++ rear; rear <= len; ++ head, ++ rear)
    {
        record[head] = record[head-1];
        //队头出队
        if(input[head-1] == 'C' || input[head-1] == 'G')
        {
            -- record[head];
        }
        //队尾入队
        if(input[rear-1] == 'C' || input[rear-1] == 'G')
        {
            ++ record[head];
        }
    }

    int max = 0;
    int begin = 0;
    for(int i = 0; i < head; ++ i)
    {
        if(record[i] > max)
        {
            max = record[i];
            begin = i;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        putchar(input[begin+i]);
    }
    
    return 0;
}