题目描述
给一个仅含有小写英文字母的字符串s，(strlen(s)<1,000,000)。询问k次(k<10,000)。每次给出一个字母集合S，问含有且仅含有S集合中的字母的极大子串有多少个？
算法分析：
对任意i,符合以si为左端点的极大子串的集合不超过26个，我们的任务就是扫描si，将si可以确定的极大子串的集合找出来。
在从右向左扫描的过程中，我们需要维护右侧与i最近的每个字母的位置。如果某字母与si-1相等，那么这个字母和其后面的字母都不能成为极大子串了。
如果我们开2^26大小的数组，那么就暴内存了.... 需要离散化。
#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
西月弦 阅读(478)
评论(0) 编辑 收藏 引用 所属分类:
比赛感言