7.20字符串综合测试卷1

# 思路

$n$ 个字符串，求两两最长公共前缀的长度。

很简单可以想到，直接暴力肯定不行，所以想到用字典树来优化，将每个字符串插入字典树，求答案即可。

# 代码

```cpp
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

#define int ll

const int N = 3e5 + 10;

int n, ans;

string s;

struct Trie{
  int ch[N][30], tot, cnt[N];
  void Insert(const string &s){
    int x = 0;
    for(char i : s){
      cnt[x]++;
      if(!ch[x][i - 'a']){
        ch[x][i - 'a'] = ++tot;
      }
      x = ch[x][i - 'a'];
      ans += cnt[x];
    }
    cnt[x]++;
  }
}T;

signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> s;
    T.Insert(s);
  }
  cout << ans;
  return 0;
}
```

# 思路

直接 $hash$ 给每个数规定一个 $hash$ 值即可。

# 代码

```cpp
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll

const int N = 2e5 + 10;

int n, q, a[N], b[N], sum1[N], sum2[N], mp[N];

mt19937_64 Rand(time(0));

signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for(int i = 1; i <= n; i++){
    mp[i] = Rand();
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> b[i];
  }
  for(int i = 1; i <= n; i++){
    sum1[i] = sum1[i - 1] + mp[a[i]];
    sum2[i] = sum2[i - 1] + mp[b[i]];
  }
  for(int i = 1, x, y, x2, y2; i <= q; i++){
    cin >> x >> y >> x2 >> y2;
    cout << (sum1[y] - sum1[x - 1] == sum2[y2] - sum2[x2 - 1] ? "Yes" : "No") << '\n';
  }
  return 0;
}
```

# 思路

很好想到二分与单调性，但是直接二分会超时。
所以可以用哈希优化判断不同子串的出现次数的过程。

# 代码

```cpp
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10, M1 = 998244353, M2 = 1e9 + 7, B1 = 233, B2 = 39;

pair<int, int> op[N];

int a[N], n, H1[N], H2[N], P1[N], P2[N];

int Hash1(int l, int r){
    return ((H1[r] - H1[l - 1] * 1ll * P1[r - l + 1]) % M1 + M1) % M1;
}

int Hash2(int l, int r){
    return ((H2[r] - H2[l - 1] * 1ll * P2[r - l + 1]) % M2 + M2) % M2;
}

bool P(int x){
    for (int i = x; i <= n; i++)op[i - x + 1] = {Hash1(i - x + 1, i), Hash2(i - x + 1, i)};
    sort(op + 1, op + n - x + 2);
    for (int i = 2; i <= n - x + 1; i++)if (op[i - 1] == op[i])return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = c - 'a';
    }
    P1[0] = P2[0] = 1;
    for (int i = 1; i <= n; i++){
        H1[i] = (H1[i - 1] * 1ll * B1 + a[i]) % M1;
        H2[i] = (H2[i - 1] * 1ll * B2 + a[i]) % M2;
        P1[i] = (P1[i - 1] * 1ll * B1) % M1;
        P2[i] = (P2[i - 1] * 1ll * B2) % M2;
    }
    int l = 0, r = n - 1;
    while (r > l){
        int mid = l + r + 1 >> 1;
        if (P(mid))l = mid;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}
```

# 思路

为了高效地找到所有回文子串，我们使用 $Manacher$ 算法

然后在 $Manacher$ 算法的扩展过程中，对于每个位置i，如果当前回文长度可以扩展，则检查是否存在满足条件的双倍回文子串。

**优化**：在扩展过程中，只检查长度是4的倍数的子串，以减少不必要的计算。

# 代码

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int p[N], n, ans;

string s;

void Manacher(string &s, int n) {
    int c = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (i < r) {
            p[i] = min(p[2 * c - i], r - i);
        } else {
            p[i] = 1;
        }
        while (s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > r) {
            if (i & 1) {
                for (int j = max(r, i + 4); j < i + p[i]; j++) {
                    if (!((j - i) & 3) && p[i - (j - i) / 2] > (j - i) / 2) {
                        ans = max(ans, j - i);
                    }
                }
            }
            r = i + p[i];
            c = i;
        }
    }
}

int main() {
    cin >> n >> s;
    s = ' ' + s;
    s = s + s;
    for (int i = n; i >= 1; i--) {
        s[i * 2 + 1] = '#';
        s[i * 2] = s[i];
    }
    s[1] = '#';
    Manacher(s, 2 * n + 1);
    cout << ans;
    return 0;
}
```

正在渲染内容...