除了图论以外,随便做一下数据结构,感觉挺不错的
分析题目:每个子串都是,如果能插入到字典树,就答案加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; }