子串查詢

?

?Accepts: 1262

?

?Submissions: 5335

?Time Limit: 3500/3000 MS (Java/Others)

?

?Memory Limit: 262144/262144 K (Java/Others)

Problem Description

度度熊的字符串課堂開始了！要以像度度熊一樣的天才為目標，努力奮斗哦！

為了檢驗你是否具備不聽課的資質，度度熊準備了一個只包含大寫英文字母的字符串?A[1,n] = a_1 a_2 \cdots a_nA[1,n]=a?1??a?2???a?n??，接下來他會向你提出?qq?個問題?(l,r)(l,r)，你需要回答字符串?A[l,r] = a_l a_{l+1} \cdots a_rA[l,r]=a?l??a?l+1???a?r???內有多少個非空子串是?A[l,r]A[l,r]?的所有非空子串中字典序最小的。這里的非空子串是字符串中由至少一個位置連續的字符組成的子序列，兩個子串是不同的當且僅當這兩個子串內容不完全相同或者出現在不同的位置。

記?|S|∣S∣?為字符串?SS?的長度，對于兩個字符串?SS?和?TT?，定義?SS?的字典序比?TT?小，當且僅當存在非負整數?k(\leq \min(|S|,|T|))k(≤min(∣S∣,∣T∣))?使得?SS?的前?kk?個字符與?TT?的前?kk?個字符對應相同，并且要么滿足?|S| = k∣S∣=k?且?|T| > k∣T∣>k，要么滿足?k < \min(|S|,|T|)k<min(∣S∣,∣T∣)?且?SS?的第?k+1k+1?個字符比?TT?的第?k+1k+1?個字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。

Input

第一行包含一個整數?TT，表示有?TT?組測試數據。

接下來依次描述?TT?組測試數據。對于每組測試數據：

第一行包含兩個整數?nn?和?qq，表示字符串的長度以及詢問的次數。

第二行包含一個長為?nn?的只包含大寫英文字母的字符串?A[1,n]A[1,n]。

接下來?qq?行，每行包含兩個整數?l_i,r_il?i??,r?i??，表示第?ii?次詢問的參數。

保證?1 \leq T \leq 101≤T≤10，1 \leq n,q \leq 10^51≤n,q≤10?5??，1 \leq l_i \leq r_i \leq n1≤l?i??≤r?i??≤n。

Output

對于每組測試數據，先輸出一行信息 "Case #x:"（不含引號），其中 x 表示這是第?xx?組測試數據，接下來?qq?行，每行包含一個整數，表示字符串?A[l,r]A[l,r]?中字典序最小的子串個數，行末不要有多余空格。

Sample Input

1 2 3 AB 1 1 1 2 2 2

Sample Output

Copy

Case #1: 1 1 1

前綴字母A~Z的個數，復雜度（O(n)）

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #define fora(i,a,b) for(i=a;i<b;i++) #define fors(i,a,b) for(i=a;i>b;i--) #define fora2(i,a,b) for(i=a;i<=b;i++) #define fors2(i,a,b) for(i=a;i>=b;i--) #define PI acos(-1.0) #define eps 1e-6 #define INF 0x3f3f3f3ftypedef long long LL; typedef long long LD; using namespace std; const int maxn=1e5+11; char str[maxn]; int qz[maxn][33]; int main() {int T,t=0,len;scanf("%d",&T);while(T--){int n,q;scanf("%d%d%s",&n,&q,str);int i,j;len=strlen(str);fora(i,0,len){fora(j,0,26){qz[i+1][j]=qz[i][j];}qz[i+1][str[i]-'A']++;}printf("Case #%d:\n",++t);while(q--){int L,R;scanf("%d%d",&L,&R);fora(i,0,26){//printf("****%c %d %d\n",i+'A',qz[R+1][i],qz[L][i]);if(qz[R][i]-qz[L-1][i]>0){printf("%d\n",qz[R][i]-qz[L-1][i]);break;}}}}return 0; }

?

轉載于:https://www.cnblogs.com/107acm/p/9428305.html

總結

以上是生活随笔為你收集整理的2018百度之星程序设计大赛 - 资格赛 1002 子串查询的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。