现在的位置: 首页 > 综合 > 正文

CF 271D Good Substrings(trie树)

2013年08月22日 ⁄ 综合 ⁄ 共 664字 ⁄ 字号 评论关闭

除了图论以外,随便做一下数据结构,感觉挺不错的

分析题目:每个子串都是,如果能插入到字典树,就答案加1,思想比较简单,但是要注意的是,想问题要清楚,对于这道题,有一个k在限制,所以不必把所有的子串都插入,用字典树的另一个目的在于能够除重,是插入一个子串,就加1,而不是已有的子串也加1。另外,由于是子串,它不必一个一个子串完整的插入,比如说:asdfg这个字符串,as是子串,asd也是子串,这时候如果as已经被插入了,那么直接就遍历到d了把插入进去,不用从头再插一遍asd这个整个的子串。如果没明白,那就看下面的代码吧!总之要灵活

代码:

//by Molly
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5000000;
int ch[N][26], k;
char f[30], s[2000];

int main()
{
    cin >> s >> f >> k;
    memset( ch, 0, sizeof(ch) );
    int sz = 1;
    long long ans = 0;
    for ( int i = 0; i < strlen(s); ++i ) {
        int u = 0, cnt = 0, c;
        for ( int j = i; j < strlen(s); ++j ) {
            c = s[j] - 'a';
            if ( f[c] == '0' ) {
                if ( ++cnt > k ) break;
            }
            if ( !ch[u][c] ) {
                ch[u][c] = sz++;
                ans++;
            }
            u = ch[u][c];
        }
    }
    cout << ans << endl;
}

抱歉!评论已关闭.