蓝桥杯 子串分值(难)

题目描述

对于一个字符串 SS,我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。例如 f(aba) = 1,f(abc) = 3, f(aaa) = 0f(aba)=1,f(abc)=3,f(aaa)=0。

蓝桥杯 子串分值(难)

输入描述

输入一行包含一个由小写字母组成的字符串 S。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入:ababc

输出:21

代码:

#include<stdio.h>        
#include<string.h>
#define N 100002
int main()
{
    char s[N];
    int last[26];    //记录 a~z中每个字符最后被扫描的位置,即下标 
    int pre[N];        //记录前面与第i个字符相同的字符的位置,即下标 
    int next[N];    //记录后面与第i个字符相同的字符的位置,即下标 
    gets(s);
    int k,i,l;
    int sum=0;        //sum=sum+(i-pre[i])*(next[i]-i)  
    l=strlen(s);    //字符串长度
    for(i=0; i<26; i++)    //由于下标从0开始,所有字符在没出现第一次前都是 -1 
        last[i]=-1;
        
    for(i=0; i<l; i++)
    {
        k=s[i]-'a';
        pre[i]=last[k];    //前面与第i个字符相同的字符的位置
        last[k]=i;    //更新字符的位置 
    }
    
    for(i=0; i<26; i++)    //由于下标从0开始,从后面到前面,所有字符在没出现第一次前都是 l
        last[i]=l;
        
    for(i=l-1; i>=0; i--)
    {
        k=s[i]-'a';
        next[i]=last[k];    //后面与第i个字符相同的字符的位置
        last[k]=i;    //更新字符的位置 
    }
    
    for(i=0; i<l; i++)
    {
        sum+=(i-pre[i])*(next[i]-i);
        //(i-pre[i])为前面与第i个字符相同的字符与s[i]的距离
        //(next[i]-i)为后面与第i个字符相同的字符与s[i]的距离
    }
    printf("%d",sum);
    return 0;
}

题目链接:子串分值 - 蓝桥云课 (lanqiao.cn)

上一篇:2100306-76-9,N-(Azido-PEG3)-N-Biotin-PEG4-methyl ester具有生物素基团和末端叠氮基的支化PEG连接物


下一篇:让程序员最头疼的5种编程语言