A - Similar Strings HDU - 6485

3-Day1-A
Putting two similar strings together will create a very strong power that can quake the earth into parts and the person who did that can be called the Destroyer of the World. In order to stop the Destroyer of the World, WNJXYK decided to check every string in this world to make sure there is no pair of strings are similar. But some strings are too long that WNJXYK cannot judge whether they are similar to others, so he turns to you for help.
Now WNJXYK need you to determine the maximum s, for string A has a substring A’ and string B has a substring B’ whose length are both s and they differ on at most K positions.
Input
The input starts with one line contains exactly one positive integer T which is the number of test cases.
Each test case contains three lines. The first line contains an integer K and each of the following two lines contains a string indicates stringA or stringB
Output
For each test case, output one line containing “y” where y is the maximum s.
Sample Input
3
3
qwertypoi
qwetyrio
0
qqqqq
qqqaqqqq
10
qwertyuiop
asdfghjklzxcvbnm
Sample Output
6
4
10

Hint
1<=T<=5,1<=len(A),len(B)<=4000,0<=K<=min{len(A),len(B)}
Strings only contain lowercase English letters.

题意：
为了阻止世界毁灭者，WNJXYK决定检查世界上的每一根字符串，以确保没有一对字符串是相似的。但有些字符串太长，WNJXYK无法判断它们是否与其他字符串相似，因此他向您寻求帮助。
现在WNJXYK需要您确定最大值s，因为字符串A有一个子字符串A'，而字符串B有一个子字符串B'，其长度都是s，并且它们在最多K个位置上不同。

输出
对于每个测试用例，输出一y是最大子字符串长度。

思路：尺取法，记录每种字母出现的次数，并用记录不同字母的个数。如果右移使此字母的 cntcnt 值由零变成一， curcur 值就加一；如果左移使此字母的 cntcnt 值由一变成零， curcur 值就减一。右移至 cur≥kcur≥k 时累计答案。

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxs=5010;
int ks;
char str1[maxs],str2[maxs];
int ans;
void funs(char str11[], char str22[])
{
    int l=min(strlen(str11),strlen(str22));
    int t=0,k=-1;
    for (int i=0;i<l;i++)
    {
        while (k+1<l)
        {
            if (str11[k+1]!= str22[k+1])
            {
                if (t+1>ks)
                    break;
                t++;
            }
            k++;
        }
        ans=max(ans,k-i+1);
        if (str11[i] != str22[i])
            t--;
    }
}
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        ans = 0;
        cin>>ks;
        cin>>str1>>str2;
        int l=strlen(str1);
        for (int i=0;i<l;i++)
            funs(str1+i,str2);
        l=strlen(str2);
        for (int i=0;i<l;i++)
            funs(str2+i,str1);
        cout<<ans<<endl;
    }
    return 0;
}