題目描述
給一個僅含有小寫英文字母的字符串s，(strlen(s)<1,000,000)。詢問k次(k<10,000)。每次給出一個字母集合S，問含有且僅含有S集合中的字母的極大子串有多少個？
算法分析：
對任意i,符合以si為左端點的極大子串的集合不超過26個，我們的任務就是掃描si，將si可以確定的極大子串的集合找出來。
在從右向左掃描的過程中，我們需要維護右側與i最近的每個字母的位置。如果某字母與si-1相等，那么這個字母和其后面的字母都不能成為極大子串了。
如果我們開2^26大小的數(shù)組，那么就暴內(nèi)存了.... 需要離散化。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = (
int)1e6+10;
const int M = 10005;
char ch[N];
int m,hash[M],flag[M],Q[M];
int find(
int v){
int l=0,r = m-1;
while(l<r){
int mid = l+r >>1;
if(hash[mid] >= v) r = mid;
else l = mid+1;
}
return hash[r] == v ? r : -1;
}
int main(){
while(~scanf("%s",ch)){
int n = strlen(ch);
int msk; cin >> m;
char c[50];
for(
int i=0;i<m;i++){
scanf("%s",c);
msk = 0;
int k = strlen(c);
for(
int j=0;j<k;j++) msk |= 1<<c[j]-'a';
hash[i] = Q[i] = msk;
}
sort(hash,hash+m);
int nxt[27];
memset(nxt,-1,
sizeof(nxt));
memset(flag,0,
sizeof(flag));
for(
int i=n-1;i>=0;i--){
int x = 1<<ch[i]-'a';
int y = i == 0 ? -1 : 1<<ch[i-1] - 'a';
for(
int j=0;j<27;j++)
if(nxt[j]==-1 || nxt[j]== x){
for(
int k=j;k;k--) nxt[k] = nxt[k-1];
nxt[0] = x;
break;
}
int msk = 0,p;
for(
int j=0;nxt[j]!=-1 && nxt[j]!= y;j++){
msk |= nxt[j];
if((p = find(msk))!=-1)
flag[p] ++;
}
}
for(
int i=0;i<m;i++)
printf("%d\n",flag[find(Q[i])]);
}
}
posted on 2012-07-22 16:18
西月弦 閱讀(514)
評論(0) 編輯 收藏 引用 所屬分類:
比賽感言