Gym – 101164C Castle KMP的拓展、next数组+dp、好题

Problem C Castle KMP的拓展、next数组+dp、好题

Source

ACM-ICPC Southeastern European Regional Programming Contest
Bucharest, Romania – Vinnytsya, Ukraine

Gym - 101164C

My Solution

题意：给出原串s，然后有3种操作，1、在s的末尾加上一个小写字母ch；2、把s的拷贝放入set；3、询问在set中的字符串是当前字符串s‘的后缀的个数。

KMP的拓展、next数组+dp

用构造出的最终串，跑出该字符串的next数组nxt[MAXN]，并记录l[i] 为到操作i时字符串s的长度。

然后对于操作i = 1 ~ e，如果该操作是type2则标记f[i] = true, 并且对于每个i， u = l[i], ans = sum[u] = f[i] + sum[nxt[u]],然后如果是type三则把ans输出即可。

其中sum[u]表示到长度为u时的在set中的字符串是当时串的后缀的个数，这里应用KMP的next[i]表示最长的前缀==后缀来进行状态转移。

复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1.2e6 + 8;

string s;
int nxt[MAXN];
inline void get_nxt(const string& pattern)
{
    int n = pattern.size();
    for(int i = 1, j = 0; i < n; i++){ j = i; while(j > 0){
            j = nxt[j];
            if(pattern[j] == pattern[i]){
                nxt[i + 1] = j + 1;
                break;
            }
        }
    }
}
int type[MAXN], l[MAXN], sum[MAXN];
bool f[MAXN];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, e, i;
    char ch;
    cin >> n >> e;
    cin >> s;
    for(i = 0; i < e; i++){ cin >> type[i];
        if(type[i] == 1){
            cin >> ch;
            s += ch;
            n++;
        }
        l[i] = n;
    }
    int len = s.size(), u, ans;
    get_nxt(s);
    for(i = 0; i < e; i++){
        if(type[i] == 2){
            f[l[i]] = true;
        }
        u = l[i];
        ans = sum[u] = f[u] + sum[nxt[u]];
        if(type[i] == 3) cout << ans << "n";
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}