hdu5672 找字符串的子串问题

迈不过友情╰ 2022-08-21 11:40 136阅读 0赞

题目：给一个字符串，问有多少个子串至少含有k个不同的字母？

有一个明显的性质：如果子串(i,j)包含了至少m个不同的字符，那么子串(i,k),(j<k<length)也包含了至少m个不同字符。  
  
因此对于每一个左边界，只要找到最小的满足条件的右边界，就能在O(1)时间内统计完所有以这个左边界开始的符合条件的子串。  
  
寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，同时累加答案即可。

#include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int maxn = 1000005 ; 
    char str[maxn] ; 
    int vis[100] ; 
    int m ; 
    
    int main()
    {
    	int t ; 
    	scanf("%d",&t) ; 
    	while(t--)
    	{
    		scanf("%s%d",str,&m) ; 
    		int n = strlen(str);
    		memset(vis,0,sizeof(vis));
    		int flag = 0 ;   //指向后面的下标
    		int num = 0 ;    //不同字符的个数
    		long long ans = 0 ; 
    		for(int i = 0 ; i < n ; i++)
    		{   //计算每个以str[i]为开始字符的子串是否满足条件
    			while(num<m&&flag<n)
    			{
    				vis[str[flag]-'a']++ ; 
    				if((vis[str[flag]-'a'])==1)num++;
    				flag++;
    			}
    			if(num==m)ans += n - flag + 1 ;
    			vis[str[i]-'a']-- ; 
    			if((vis[str[i]-'a'])==0)num--;
    		}
    		printf("%I64d\n",ans) ; 
    	}
    	return 0 ; 
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Java字符串处理问题：截取子串失败示例

在Java中，我们经常使用`substring()`方法来截取字符串的子串。但如果操作不正确，可能会导致截取失败。下面是一个示例： ```java String str =

清疚/ 2024年09月27日 23:30/ 0 赞/ 55 阅读

相关 Java字符串操作问题：替换子串示例

在Java中，处理字符串并替换子串通常使用`String`类的`replace()`方法。这里有一个简单的示例： ```java public class Main {

淩亂°似流年/ 2024年09月27日 23:03/ 0 赞/ 49 阅读

相关 Java字符串操作：截取子串问题解析

在Java中，处理字符串并截取子串主要涉及到`String`类的一些方法。以下是一些常见问题及解析： 1. **如何获取字符串的长度**： ```java Str

比眉伴天荒/ 2024年09月15日 03:27/ 0 赞/ 59 阅读

相关华为OD机试 - 找出符合要求的字符串子串（Java）

题目描述给定两个字符串，从字符串2中找出字符串1中的所有字符，去重并按照ASCII值从小到大排序。输入字符串1：长度不超过1024 输入字符串2：长度不超过100

朱雀/ 2024年03月17日 13:51/ 0 赞/ 40 阅读

相关子串查找（字符串匹配）

子串查找（字符串匹配） package com.company; public class Character {

╰半橙微兮°/ 2022年09月01日 13:48/ 0 赞/ 256 阅读

相关 hdu5672 找字符串的子串问题

题目：给一个字符串，问有多少个子串至少含有k个不同的字母？有一个明显的性质：如果子串(i,j)包含了至少m个不同的字符，那么子串(i,k),(j<k<length)也包含了

迈不过友情╰/ 2022年08月21日 11:40/ 0 赞/ 137 阅读

相关 hdu 2846 统计给定字符串是多少字符串的子串

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2846][http_acm.hdu.edu.cn_showprobl

不念不忘少年蓝@/ 2022年08月05日 11:21/ 0 赞/ 154 阅读

相关找出字符串中的最长连续数字子串

题目 > 给出一个字符串作为输入，找出其中最长的连续数字串并返回其长度和起始index。如果存在长度相同的连续数字串，返回最后一个连续数字串。如果没有，返回0和0。

怼烎@/ 2022年06月08日 05:27/ 0 赞/ 206 阅读

相关在一个字符串中，找出最长回文子串

在一个字符串中，找出最长回文子串(manacher算法) 时间复杂度O(n) 空间复杂度O(n) 比如12321，先做预处理:\1\2\3\2\1\ 定义

桃扇骨/ 2022年06月08日 00:54/ 0 赞/ 185 阅读

相关 leetcode 686. Repeated String Match 字符串迭代找子串

Given two strings A and B, find the minimum number of times A has to be repeated such th

た入场券/ 2022年06月03日 08:28/ 0 赞/ 148 阅读