kickstart2018 round F common Anagrams

題意：

給定兩個相同長度L的字元串A和B，有多少個不同的A的子串可以在B中找到一個子串是它的“相同字母異序詞”。

相同字母異序詞： 字元串的長度相同，且組成字元串的字元以及字元出現的次數也相同；例如：ABBA和BABA；

原題連結：https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e07/00000000000510f2

解法：

1.字首和思想

首先計算字元串A和B對應的字首和，其次依次選取A中一個對應的子串，然後周遊字元串B，時間複雜度：O(26*n^3);

C++代碼如下：

#include<iostream>

#include<vector>

#include<string>

#include<map>

using namespace std;

int core(string A, string B){

    int n = A.size();

    vector<vector<int>> pre_A(n + 1, vector<int>(26, 0)), pre_B(n + 1, vector<int>(26, 0));

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

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

            if (j == A[i - 1] - 'A') pre_A[i][j] = pre_A[i - 1][j] + 1;

            else pre_A[i][j] = pre_A[i - 1][j];

        }

    }

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

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

            if (j == B[i - 1] - 'A') pre_B[i][j] = pre_B[i - 1][j] + 1;

            else pre_B[i][j] = pre_B[i - 1][j];

        }

    }

    int res = 0;

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

        for (int j = i - 1; j >= 0; j--){

            int temp = i - j;

            for (int k = 0; k<=n-temp; k++){

                int flag = 0;

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

                    if ( pre_A[i][count] - pre_A[j][count] != pre_B[k + temp][count] - pre_B[k][count]){

                        flag = 1;

                        break;

                    }

                }

                if (flag == 0){

                    res++;

                    break;

                }

            }

        }

    }

    return res;

}

int main(){

    int T;

    cin >> T;

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

        int N;

        cin >> N;

        string A, B;

        cin >> A >> B;

        int res = core(A, B);

        cout << "Case #" << i + 1 << ": " << res << endl;

    }

    return 0;

}

2.