程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5056 雙指針（也叫窗口滑動（也叫尺取法))

HDU 5056 雙指針（也叫窗口滑動（也叫尺取法))

編輯：關於C++

Description

You are given a string S consisting of lowercase letters, and your task is counting the number of substring that the number of each lowercase letter in the substring is no more than K.

Input

In the first line there is an integer T , indicates the number of test cases.
For each case, the first line contains a string which only consist of lowercase letters. The second line contains an integer K.

[Technical Specification]
1<=T<= 100
1 <= the length of S <= 100000
1 <= K <= 100000

Output

For each case, output a line contains the answer.

Sample Input

3
abc
1
abcabc
1
abcabc
2

Sample Output

6
15
21

此題允許不同位置上的相同字母算作不同種類

雙指針（也叫窗口滑動（也叫尺取法)):
定義兩個指針，始終保持指針內的子串符合題目要求，向右移動右指針，若不符合要求，則將左指針向右移動直到指針內的子串符合題目要求為止。這樣就求出了每個點向左延伸最遠符合要求的點，於是這個區間內的任意一個子串都是符合題目要求的，不斷累加即可。
復雜度：O（n）.

#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f

using namespace std;

char s[1000000];
int vis[100];
int main()
{
    int T,a;
    while(~scanf(%d,&T))
    {
        while(T--)
        {
            long long sum=0;
            scanf(%s%d,s,&a);
            memset(vis,0,sizeof(vis));
            int len=strlen(s);
            int pos=0;                        //左指向
            for(int i=0; ia)
                {
                    while(s[i]!=s[pos])
                    {
                        vis[s[pos]-'a']--;
                        pos++;
                    }
                    vis[s[pos]-'a']--;
                    pos++;
                }
                sum+=i-pos+1;
            }
            printf(%I64d
,sum);
        }
    }
}
/*
 例如 abcabc 1

                 a       ab          abc        bca        .....
 sum+     1      2        3           3           3
                 a        b           c           a
					      ab         bc          ca
									abc         bca
 故15種
*/