算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述
   给一个仅含有小写英文字母的字符串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 西月弦 阅读(486) 评论(0)  编辑 收藏 引用 所属分类: 比赛感言

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理