蓝桥杯 5.字符串

蓝桥杯 5.字符串

文章目录

  • 蓝桥杯 5.字符串
    • KMP&字符串哈希
    • Manacher
    • 编程138-148
    • 字典树基础
    • 01Trie
    • 编程149-155

KMP&字符串哈希

KMP算法

  • 字符串匹配算法, 用于匹配**模式串P(短)和文本串S(长)**中出现的所有位置, 例如, S = “ababac”, P = “aba”, 那么出现的所有位置就是1和3
  • 初学KMP时, 只需记住和学会使用模板即可, 对其原理不需要过度深究
  • KMP算法将原本O(n^2)的字符串匹配算法优化到了O(n), 其中精髓在于next数组(仅与模式串P有关), next数组表示此时模式串下标失配时应该移动到的位置, 也表示最长的相同真前后缀的长度
// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
char s[N], p[M];
int nex[M];
int n = strlen(s + 1), m = strlen(p + 1);
nex[0] = nex[1] = 0; // 初始化
for(int i = 2, j = 0; i <= m; i++){
    // 不断匹配p[i]和p[j + 1]
    while(j && p[i] != p[j + 1]) j = nex[j]; // 失配
    if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
    nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
}



// 通过next数组进行匹配
for(int i = 1, j = 0; i <= n; i++){
    while(j && s[i] != p[j + 1]) j = nex[j]; // 失配
    if(s[i] == p[j + 1]) j++;
	if(j == m) // 成功匹配一次
}

例题讲解

image-20250224175120346

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];
char s[N], p[N];


int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> p >> s;
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  int nex[N];
  int n = strlen(s + 1), m = strlen(p + 1);
  nex[0] = nex[1] = 0; // 初始化
  for(int i = 2, j = 0; i <= m; i++){
      // 不断匹配p[i]和p[j + 1]
      while(j && p[i] != p[j + 1]) j = nex[j]; // 失配
      if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }


  ll ans = 0;
  // 通过next数组进行匹配
  for(int i = 1, j = 0; i <= n; i++){
      while(j && s[i] != p[j + 1]) j = nex[j]; // 失配
      if(s[i] == p[j + 1]) j++;
      if(j == m) ans++; // 成功匹配一次
  }
  cout << ans << "\n";
  return 0;
}

字符串哈希

  • (基于进制的)字符串Hash本质上是用一个数字表示一段字符串, 从而降低字符串处理的复杂度
  • 这个数字是一个很大的数字, 采用unsigned int 类型, 可以自然溢出, 从而简化了去模的部分
  • 还需要一个进制数base, 用于规定这个数字的进制
  • Hash数组h[i]表示字符串s[1~i]的Hash值, 采用类似前缀和的形式以便于求出任意一个子串的Hash值
// 字符串Hash初始化:
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h[N];
char s[N];
for(int i = 1; i <= n; i++) h[i] = h[i - 1] * base + s[i] - 'A' + 1;


// 获取子串s[l]~s[r]的Hash:
ull getHash(int l, int r){
    return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}

例题讲解

  • 还是上一道题, 1.斤斤计较的小Z
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h1[N], h2[N], b[N];
char s[N], p[N];

// 获取子串s[l]~s[r]的Hash:
ull getHash(ull h[], int l, int r){
    return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> p >> s;
  int nex[N];
  int n = strlen(s + 1), m = strlen(p + 1);
  b[0] = 1;
  // 字符串Hash初始化:
  for(int i = 1; i <= n; i++) {
    b[i] = b[i - 1] * base;
    h1[i] = h1[i - 1] * base + (int)p[i];
    h2[i] = h2[i - 1] * base + (int)s[i];
  }
  int ans = 0;
  for(int i = 1; i + m - 1 <= n; i++){
    if(getHash(h1, 1, m) == getHash(h2, i, i + m - 1)) ans++;
  }
  cout << ans << "\n";

  return 0;
}

Manacher

回文串的性质

  • 类似AABAA, 对于每个i具有s[i] = s[n + 1 - i]的字符串
  • 回文半径: 对于一个回文中心i, 如果他的半径为r, 如果他为奇数长度的回文串的中心, 则说明[i - r + 1, i + r - 1]为一个回文串, 如果i是偶数长度的回文中心, 则回文半径没有意义(Manacher算法会解决这个问题)
  • 回文的递归性质: 某个点的回文半径相比关于某个回文中心的点的回文半径一定相等或更大

Manacher算法

  • ABBA没有回文半径, Manacher就是将所有的回文串转换成奇数长度的回文串, 方法是在字符串中间和头尾插入特殊字符, 转换后变成了^#A#B**#B#A$, 这个回文串是以黑色#**为回文中心, 以5为回文半径的, 它就表示原回文串中的回文长度为5-1=4
  • 位置i的回文半径以p[i]表示, 意思是在转换后的字符串中[i-p[i]+1, i+p[i]-1]是回文的

image-20250224203718876

image-20250224204600117

int c = 0, r = 0; // 初试都从0开始
for(int i = 1; i <= 2 * n + 1; i++){
    p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;
    // 如果p[i]可以更大, 就持续更新
    while(s[i + p[i]] == s[i - p[i]]) p[i]++;
    // 如果此时i可以作为一个更好的c, 就替换
    if(i + p[i] > r) c = i, r = i + p[i];
}

例题讲解

image-20250224213138138

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
int p[N];
char s[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> s + 1;
  int c = 0, r = 0; // 初试都从0开始
  int n = strlen(s + 1);

  // 添加符号, 使其成为Manacher字符串
  for(int i = 2 * n + 1; i >= 1; i--){
    s[i] = (i & 1) ? '#' : s[i >> 1];
  }
  s[0] = '^', s[2 * n + 1] = '$';

  for(int i = 1; i <= 2 * n + 1; i++){
      p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;
      // 如果p[i]可以更大, 就持续更新
      while(s[i + p[i]] == s[i - p[i]]) p[i]++;
      // 如果此时i可以作为一个更好的c, 就替换
      if(i + p[i] > r) c = i, r = i + p[i];
  }

  int ans = 0;
  for(int i = 1; i <= 2 * n + 1; i++){
    ans = max(ans, p[i] - 1);
  }
  cout << ans << "\n";
  return 0;
}

编程138-148

image-20250224224252879

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
int nex[N];

void getNext(string &p){
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  nex[0] = 0; // 初始化
  for(int i = 1, j = 0; i < p.size(); i++){
      // 不断匹配p[i]和p[j + 1]
      while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配
      if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  cin >> p;
  int ans = 0;
  getNext(p);
  for(int i = 0; i < p.size(); i++){
    ans = max(ans, nex[i]);
  }
  cout << ans << "\n";
  return 0;
}

image-20250225083049199

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p;
ll nex[N], ans;

void getNext(string &p){
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  int j = 0;
  nex[0] = 0; // 初始化
  for(int i = 1; i < p.size(); i++){
      // 不断匹配p[i]和p[j + 1]
      while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配
      if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
}

ll find(ll x){
  if(!nex[x]) return x + 1;
  else return nex[x] = find(nex[x] - 1);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n >> p;
  getNext(p);
  for(int i = 0; i < p.size(); i++){
    if(nex[i]) ans += (i + 1) - find(i);
  }
  cout << ans << "\n";
  return 0;
}

image-20250225092804059

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p, t;
ll nex[N], ans;
vector<ll> pre(N + 2), suf(N + 1);

void getNext(string &p){
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  int j = 0;
  nex[0] = 0; // 初始化
  for(int i = 1; i < p.size(); i++){
      // 不断匹配p[i]和p[j + 1]
      while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配
      if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
}

// 通过next数组进行匹配
int KMP(string p, string s, vector<ll> &f){
  int a = -1;
  memset(nex, 0, sizeof(nex));
  getNext(s);
  for(int i = 0, j = 0; i < p.size(); i++){
    while(j && s[j] != p[i]) j = nex[j - 1]; // 失配
    if(s[j] == p[i]) j++;

    f[i] = j;

    if(j == s.size()) j = nex[j - 1]; // 成功匹配一次

  }
  return a;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m, k; cin >> n >> m >> k >> p >> t;
  KMP(p, t, pre);

  reverse(p.begin(), p.end());
  reverse(t.begin(), t.end());

  KMP(p, t, suf);
  reverse(suf.begin(), suf.begin() + n);

  map<ll, ll> mp;
  for(int i = 0; i < n; i++){
    mp[suf[i]]++;
  }
  for(int i = 0; i < n; i++){
    mp[suf[i]]--;
    if(mp[m - pre[i]]){
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}

image-20250225093617100

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p, t;
ll nex[N], ans;

void getNext(string &p){
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  int j = 0;
  nex[0] = 0; // 初始化
  for(int i = 1; i < p.size(); i++){
      // 不断匹配p[i]和p[j + 1]
      while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配
      if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> p;
  getNext(p);

  ll tmp = p.size() - nex[p.size() - 1]; // 最小周期
  if(tmp != p.size() && p.size() % tmp == 0){ // 必须是周期的整数倍(不是的话就不能拼接成完整的字符串, 所以为1), 且和周期不相等, 相等则为1
    cout << p.size() / tmp; // 总长度/最小周期 == 最多子串的数量
  } else {
    cout << 1;
  }

  return 0;
}

142诗歌双联之谜 跟上面的诗歌双联一样, 而且比上面的题还弱了

image-20250225112351780

image-20250225095728817

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
const ll INF = 1e14 + 9;
string s, p;
// char s[N], p[N];
ll nex[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n >> s >> p;
  s += s;
  s = " " + s;
  p = " " + p;
  ll m = n; n <<= 1;
  for(int i = 1; i <= n; i++){
    if(islower(s[i])){
      s[i] = toupper(s[i]);
    } else {
      s[i] = tolower(s[i]);
    }
  }
  nex[0] = 0; // 初始化
  for(int i = 2, j = 0; i <= m; i++){
      // 不断匹配p[i]和p[j + 1]
      while(j && p[i] != p[j + 1]) j = nex[j]; // 失配
      if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
  ll ans = INF;
  for(int i = 1, j = 0; i <= n; i++){
    while(j && s[i] != p[j + 1]) j = nex[j]; // 失配
    if(s[i] == p[j + 1]) j++;
    if(j == m) {// 成功匹配一次
      ans = min({ans, i - m, 2 * m - i});
      // ans = min(ans, i - m);
    }
  }
  if(ans == INF) cout << "No\n";
  else cout << "Yes\n" << ans << "\n";

  return 0;
}

image-20250225131849521

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
ll nex[N], f[N];

void getNext(string &p){
  // 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
  nex[0] = 0; // 初始化
  for(int i = 1, j = 0; i < p.size(); i++){
      // 不断匹配p[i]和p[j + 1]
      while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配
      if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移
      nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n >> p;
  ll ans = 0;
  getNext(p);
  for(int i = 0; i < n; i++){
    f[i] = 1;
  }
  for(int i = n; i >= 0; i--){
    f[nex[i] - 1] += f[i];
  }
  for(int i = 0; i < n; i++){
    ans += f[i];
  }
  cout << ans << "\n";
  return 0;
}

image-20250225145916491

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 200010;
const int base = 131; // base一般为一个质数
ull h1[N], h2[N], p[N];
int n;
char s[N];

// 获取子串s[l]~s[r]的Hash:
ull getHash1(int l, int r){
    return h1[r] - h1[l - 1] * p[r - l + 1];
}
ull getHash2(int l, int r){
  l = n - l + 1, r = n - r + 1;
    return h2[r] - h2[l - 1] * p[r - l + 1]; // 得到反转字符串的Hash值
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> s + 1;
  n = strlen(s + 1) * 2 + 1;

  // 添加符号, 使其成为Manacher字符串
  for(int i = n - 1; i; i -= 2){
    s[i + 1] = 'z' + 1;
    s[i] = s[i / 2];
  }
  s[1] = 'z' + 1;

  p[0] = 1;
  for(int i = 1, j = n; i <= n; i++, j--){ // 处理Hash
    h1[i] = h1[i - 1] * base + s[i] - 'a' + 1;
    h2[i] = h2[i - 1] * base + s[j] - 'a' + 1;
    p[i] = p[i - 1] * base;
  }
  int ans = 0;
  for(int i = 1; i <= n; i++){
      int l = 0, r = min(i - 1, n - i);
      while(l < r){
        int mid = l + r + 1 >> 1;
        if(getHash1(i - mid, i - 1) != getHash2(i + mid, i + 1)) {
          r = mid - 1;
        } else {
          l = mid;
        }
      }
      int len = i - l - 1;
      if(getHash1(1, len) == getHash2(n, n - len + 1)){
        if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);
        else ans = max(ans, l + len / 2 * 2);
      }
      len = n - (i + l);
      if(getHash1(1, len) == getHash2(n, n - len + 1)){
        if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);
        else ans = max(ans, l + len / 2 * 2);
      }
  }

  cout << ans << "\n";
  return 0;
}

146-148没写

字典树基础

朴素字符串查找

  • 给n个字符串s1~sn, 再给1个字符串t, 如何快速查找t是否在s中出现过
  • 朴素的方法是循环遍历s1~sn, 并比较si是否和t相等即可, 但是这个时间复杂度会比较大, 可能会超时

字典树

  • 字典树也叫Trie树, 是一种树形结构, 其中每个节点可以存储(当然也可以不存储)一些变量用于表示该字符串的数量, 下图中节点上的数字表示结点编号, 每条边表示一个字符
  • 建立一棵这样的树
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 2; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)
  • 编写insert函数, 用于将一个字符串s加入进去
void insert(char s[]){ // 长度为n的字符串s插入到trie中
    int n = strlen(s + 1);
    int x = 1; // 从1开始往下走
    for(int i = 1; i <= n; i++){
        // 先检查x是否存在s[i]的边
        if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;
        x = nex[x][s[i] - 'a']; // x移动到新点上
    }
    cnt[x]++;
}
  • 编写一个check函数, 用于判断某个字符串在trie中的出现的次数
int check(char s[]){
    int n = strlen(s + 1);
    int x = 1;
    for(int i = 1; i <= n; i++) x = nex[x][s[i] - 'a'];
    return cnt[x];
}

image-20250225150840886

例题讲解

image-20250225194822820

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e6 + 5;

int nex[N][26];
int cnt[N];
int idx = 2;

void insert(char s[]){ // 长度为n的字符串s插入到trie中
    int x = 1; // 从1开始往下走
    for(int i = 1; s[i]; i++){
        // 先检查x是否存在s[i]的边
        if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;
        x = nex[x][s[i] - 'a']; // x移动到新点上
    }
    cnt[x]++;
}

bool check(char s[]){
    int x = 1;
    for(int i = 0; s[i]; i++) x = nex[x][s[i] - 'a'];
    return x;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++){
    char s[N]; cin >> s + 1;
    insert(s);
  }
  for(int y = 1; y <= m; y++){
    char t[N]; cin >> t;
    cout << (check(t) ? "Y" : "N") << "\n";
  }

  
  return 0;
}

01Trie

介绍

image-20250225195251885

image-20250225195724410

插入

image-20250225200024615

查询

image-20250225200834947

例题讲解

image-20250225202143690

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;

void insert(int x){
  int o = 1;
  for(int i = 30; i >= 0; i--){
    int y = x >> i & 1;
    if(!son[o][y]) son[o][y] = ++tot;
    o = son[o][y];
  }
}
int query(int x){
  int o = 1, res = 0;
  for(int i = 30; i >= 0; i--){
    int y = x >> i & 1;
    if(son[o][!y]) o = son[o][!y], res |= (1 << i);
    else o = son[o][y];
  }
  return res;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    prefix[i] = prefix[i - 1] ^ a[i];
  }
  insert(0);
  int ans = 0;
  for(int i = 1; i <= n; i++){
    ans = max(ans, query(prefix[i]));
    insert(prefix[i]);
  }
  cout << ans << "\n";
  
  return 0;
}

编程149-155

image-20250226194440596

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
string s;
map<string, ll> mp;

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> s;
    mp[s]++;
  }
  for(auto it : mp){
    if(it.second >= 2){
      cout << 1 << "\n";
      return 0;
    }
  }
  cout << 0 << "\n";
    
  return 0;
}

image-20250226201953849

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
string s[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)

void insert(string &s){ // 长度为n的字符串s插入到trie中
    int n = s.length();
    int x = 0; // 从1开始往下走
    for(int i = 0; i < n; i++){
        // 先检查x是否存在s[i]的边
        if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;
        x = nex[x][s[i] - 'a']; // x移动到新点上
        cnt[x]++;
    }
    
}

int check(string &s){
    int n = s.length();
    int x = 0, dep = 0, mx = 0;
    for(int i = 0; i < n; i++){
      x = nex[x][s[i] - 'a'];
      dep++;
      if(cnt[x] >= 2){
        mx = max(mx, dep);
      }
    } 
    return mx;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> s[i];
    insert(s[i]);
  }
  for(int i = 1; i <= n; i++){
    cout << check(s[i]) << "\n";
  }
  
    
  return 0;
}

image-20250226203331654

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string s[N];
string t[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)

void insert(string &s){ // 长度为n的字符串s插入到trie中
    int n = s.length();
    int x = 0; // 从1开始往下走
    for(int i = 0; i < n; i++){
        // 先检查x是否存在s[i]的边
        if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;
        x = nex[x][s[i] - 'a']; // x移动到新点上
        cnt[x]++;
    }
    
}

int check(string &s){
    int n = s.length();
    int x = 0, dep = 0, mx = 0;
    for(int i = 0; i < n; i++){
      if(nex[x][s[i] - 'a']){
        x = nex[x][s[i] - 'a']; // 能走就走
      } else {
        return 0; // 走不了则0
      }
      
    } 
    return cnt[x];
    
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> s[i];
    insert(s[i]);
  }
  for(int i = 1; i <= m; i++){
    cin >> t[i];
    cout << check(t[i]) << "\n";
  }
  
    
  return 0;
}

image-20250226210303571

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;

void insert(int x){
  int o = 1;
  for(int i = 30; i >= 0; i--){
    int y = x >> i & 1;
    if(!son[o][y]) son[o][y] = ++tot;
    o = son[o][y];
  }
}
int query(int x){
  int o = 1, res = 0;
  for(int i = 30; i >= 0; i--){
    int y = x >> i & 1;
    if(son[o][!y]) o = son[o][!y], res |= (1 << i);
    else o = son[o][y];
  }
  return res;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    insert(a[i]);
  }
  ll q; cin >> q;
  
  for(int i = 1; i <= q; i++){
    ll x; cin >> x;
    cout << query(x) << "\n";
  }
  
  
  return 0;
}

153-155没写

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/978290.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

AI智能体与大语言模型：重塑SaaS系统的未来航向

AI智能体与大语言模型：重塑SaaS系统的未来航向

在数字化转型的浪潮中&#xff0c;软件即服务&#xff08;SaaS&#xff09;系统一直是企业提升效率、优化业务流程的重要工具。随着AI智能体和大语言模型&#xff08;LLMs&#xff09;的迅速发展&#xff0c;SaaS系统正迎来前所未有的变革契机。本文将从AI智能体和大语言模型对…
阅读更多...
Jmeter聚合报告导出log文档，Jmeter聚合报告导出到CSV

Jmeter聚合报告导出log文档，Jmeter聚合报告导出到CSV

Jmeter聚合报告导出log文档 在Filename中输入 EKS_perf_log\\${type}_log\\${__P(UNIQUEID,${__time(YMDHMS)})}\all-graph-results-log.csv 可以得到执行的log&#xff0c;文件夹包含时间戳 Jmeter聚合报告导出到CSV 点击Save Table Data&#xff0c;保存到CSV文件中
阅读更多...
基于SpringBoot的“古城景区管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“古城景区管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“古城景区管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统整体功能图 系统首页界面 系统注册界面 景…
阅读更多...
第五项修炼：打造学习型组织

第五项修炼：打造学习型组织

“没有哪个教室比得上一个充满问题的团队。” — 彼得圣吉 最近有伙伴问我们&#xff0c;如何在组织中践行《第五项修炼&#xff1a;打造学习型组织》&#xff1f;我想和大家分享的是&#xff0c;这不仅仅是“学习”&#xff0c;更是通过结构和行为的深度结合&#xff0c;推动绩…
阅读更多...
ubuntu22.04的docker容器中安装ssh服务

ubuntu22.04的docker容器中安装ssh服务

ubuntu22.04的docker容器中安装ssh服务&#xff0c;以便外部可以连接到容器中操作。 rootnode15:~# cat /etc/issue Ubuntu 22.04.5 LTS \n \l rootnode15:~# docker ps|grep qwen 7d3c36c37d36 vllm/vllm-openai:v0.7.3 "python3 -m …
阅读更多...
LabVIEW 中 codeGenEngine.llb 工具库

LabVIEW 中 codeGenEngine.llb 工具库

codeGenEngine.llb 是 LabVIEW 2019 安装目录下C:\Program Files (x86)\National Instruments\LabVIEW 2019\vi.lib\Platform\路径下的工具库&#xff0c;主要用于代码生成相关的操作&#xff0c;帮助开发者在 LabVIEW 项目中便捷地实现自动化代码生成任务&#xff0c;提高开发…
阅读更多...
基于LangChain4j调用火山引擎DeepSeek R1搭建RAG知识库实战指南

基于LangChain4j调用火山引擎DeepSeek R1搭建RAG知识库实战指南

基于LangChain4j调用火山引擎DeepSeek R1搭建RAG知识库实战指南 基于LangChain4j调用火山引擎DeepSeek R1搭建RAG知识库实战指南 基于LangChain4j调用火山引擎DeepSeek R1搭建RAG知识库实战指南一、注册火山引擎账号二、RAG技术核心原理三、环境与工具准备1. 核心组件2. 依赖配…
阅读更多...
基于YOLO11深度学习的医学X光骨折检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】

基于YOLO11深度学习的医学X光骨折检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…
阅读更多...
Unity百游修炼(2)——Brick_Breaker详细制作全流程

Unity百游修炼(2)——Brick_Breaker详细制作全流程

一、项目简介 Brick Breaker 是一款经典的打砖块游戏&#xff0c;本次案例将使用 Unity 引擎来实现该游戏的核心功能。 游戏画面如下&#xff1a; Brick_ breaker 二、项目结构概览和前期准备 &#xff08;1&#xff09;在 Unity 项目视图中&#xff0c;我们可以看到几个重要…
阅读更多...
DeepSeek开源周Day2：DeepEP - 专为 MoE 模型设计的超高效 GPU 通信库

DeepSeek开源周Day2：DeepEP - 专为 MoE 模型设计的超高效 GPU 通信库

项目地址&#xff1a;https://github.com/deepseek-ai/DeepEP 开源日历&#xff1a;2025-02-24起 每日9AM(北京时间)更新&#xff0c;持续五天 (2/5)&#xff01; ​ ​ 引言 在大模型训练中&#xff0c;混合专家模型&#xff08;Mixture-of-Experts, MoE&#xff09;因其动…
阅读更多...
前端面试基础知识整理（一）

前端面试基础知识整理（一）

1.vue生命周期 beforeCreate 创建 注入依赖 初始化非响应式数据 beforeCreate created 数据请求&#xff0c;初始化数据 设置全局时间监听 beforeMount挂载 模版编译完成后的调试 操作 dom初始化 操作dom初始化第三方插件 更新 在更新前查看 DOM 状态&#xff0c;不建议修改数据…
阅读更多...
【单片机】MSP430MSP432入门

【单片机】MSP430MSP432入门

文章目录 0 前言1 开发方式选择2 CCS和开发相关软件3 Keil开发MSP4324 IAR for 430开发MSP4305 总结 0 前言 最近因为想学DSP&#xff0c;所以把之前卸载的CCS给装回来了&#xff0c;手头也还有之前电赛剩下的MSP430和MSP432的板子&#xff0c;由于年代久远&#xff0c;想着花点…
阅读更多...
【Linux探索学习】第二十七弹——信号（上）：Linux 信号基础详解

【Linux探索学习】第二十七弹——信号（上）：Linux 信号基础详解

Linux学习笔记&#xff1a; https://blog.csdn.net/2301_80220607/category_12805278.html?spm1001.2014.3001.5482 前言&#xff1a; 前面我们已经将进程通信部分讲完了&#xff0c;现在我们来讲一个进程部分也非常重要的知识点——信号&#xff0c;信号也是进程间通信的一…
阅读更多...
74道高级Java面试合集，java开发模式面试题

74道高级Java面试合集，java开发模式面试题

前言 今天我们来说说Redis为什么高性能&#xff1f;如何做高可用&#xff1f; Redis为什么这么快&#xff1f; Redis是单线程的&#xff0c;避免了多线程的上下文切换和并发控制开销&#xff1b;Redis大部分操作时基于内存&#xff0c;读写数据不需要磁盘I/O&#xff0c;所以速…
阅读更多...
【江科协-STM32】5. 输出比较

【江科协-STM32】5. 输出比较

1. 输出比较简介 OC(Output Compare)输出比较。 输出比较可以通过CNT&#xff08;CNT计数器&#xff09;与CCR寄存器值的关系&#xff0c;来对输出电平进行置1、置0或翻转的操作&#xff0c;用于输出一定频率和占空比的PWM波形。 :::tip CNT计数器是正向计数器。它只能正向累…
阅读更多...
轻量级日志管理平台Grafana Loki

轻量级日志管理平台Grafana Loki

文章目录 轻量级日志管理平台Grafana Loki背景什么是Loki为什么使用 Grafana Loki&#xff1f;架构Log Storage Grafana部署使用基于 Docker Compose 安装 LokiMinIO K8s集群部署Loki采集Helm 部署方式和案例 参考 轻量级日志管理平台Grafana Loki 背景 在微服务以及云原生时…
阅读更多...
使用 Postman 访问 Keycloak 端点

使用 Postman 访问 Keycloak 端点

1. 引言 在本教程中&#xff0c;我们将首先快速回顾 OAuth 2.0、OpenID 和 Keycloak。然后&#xff0c;我们将了解 Keycloak REST API 以及如何在 Postman 中调用它们。 2. OAuth 2.0 OAuth 2.0 是一个授权框架&#xff0c;它允许经过身份验证的用户通过令牌向第三方授予访问…
阅读更多...
WEB1~6通杀

WEB1~6通杀

##解题思路 这六道题&#xff0c;通杀了&#xff0c;只因为是PHP的特性 来&#xff0c;看web6&#xff0c;过滤最复杂的正则&#xff0c;而且不能解析成大于999的值&#xff0c;但是&#xff0c;php是弱类型的语言&#xff0c;我只要输入任意字符数字&#xff0c;最终值就为0&…
阅读更多...
I2C协议简介：串行通信的关键技术

I2C协议简介：串行通信的关键技术

目录 一、总线通信基本概念 二、I2C总线协议介绍 1. 时序图解析 &#xff08;1&#xff09;起始信号 &#xff08;2&#xff09;应答信号 &#xff08;3&#xff09;终止信号 &#xff08;4&#xff09;设备地址 &#xff08;5&#xff09;I2C传输方法 ​编辑 &#…
阅读更多...
第二十四：5.2【搭建 pinia 环境】axios 异步调用数据

第二十四：5.2【搭建 pinia 环境】axios 异步调用数据

第一步安装&#xff1a;npm install pinia 第二步&#xff1a;操作src/main.ts 改变里面的值的信息&#xff1a; <div class"count"><h2>当前求和为&#xff1a;{{ sum }}</h2><select v-model.number"n">　 // .number 这里是…
阅读更多...
最新文章

Copyright @ 2022~2023