Gym 101158D(暴力)

题意：给定两个长度为N的字符串，1<=N<=4000，求满足字符串1中的某个区间所有的字母种类和个数都与字符串2中的某个区间相同最长的区间长度。

分析：

1、预处理每个串字母个数的前缀和。

2、暴力即可。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-12;

inline int dcmp(double a, double b)

{

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 4000 + 10;

const int MAXT = 3025 + 10;

using namespace std;

char s1[MAXN], s2[MAXN];

struct Node{

    int sum[27];

    bool operator < (const Node &rhs)const{

        for(int i = 0; i < 26; ++i){

            if(sum[i] != rhs.sum[i]) return sum[i] < rhs.sum[i];

        }

        return false;

    }

    Node operator - (const Node &rhs)const{

        Node tmp;

        for(int i = 0; i < 26; ++i){

            tmp.sum[i] = sum[i] - rhs.sum[i];

        }

        return tmp;

    }

}num1[MAXN], num2[MAXN];

set<Node> st;

int main(){

    scanf("%s%s", s1 + 1, s2 + 1);

    int len1 = strlen(s1 + 1);

    int len2 = strlen(s2 + 1);

    for(int i = 1; i <= len1; ++i){

        num1[i] = num1[i - 1];

        ++num1[i].sum[s1[i] - 'a'];

    }

    for(int i = 1; i <= len2; ++i){

        num2[i] = num2[i - 1];

        ++num2[i].sum[s2[i] - 'a'];

    }

    int len = min(len1, len2);

    bool ok = false;

    for(int i = len; i >= 1; --i){

        st.clear();

        for(int j = 1; j + i - 1 <= len1; ++j){

            st.insert(num1[j + i - 1] - num1[j - 1]);

        }

        for(int j = 1; j + i - 1 <= len2; ++j){

            if(st.count(num2[j + i - 1] - num2[j - 1])){

                ok = true;

                printf("%d\n", i);

                break;

            }

        }

        if(ok) break;

    }

    if(!ok) printf("0\n");

    return 0;

}