题意
给一个含有nc个不同字母的字符串,然后求其中有多少个长度为n的不同子串.
题解
因为题目中给出了nc,即字母种类的个数。所以可以把每一个出现的字母对应为1到nc。然后把长度为n的字符串映射成为一个整数。即把这个字符串看成一个nc进制的数。
代码
#include<cstdio>
#include<cstring>
using namespace std;
#define rg register
#define sc scanf
#define pf printf
char s[1000000];
bool hs[16000005];
int n, nc; // 迷之错误, 这两行开局部变量就RE woc!@
int toInt[256+50]; // 转化成十进制, 再用哈希标记
int main ( ) {
sc( "%d %d %s", &n, &nc, s );
rg int cnt = 0;
for ( rg int i = 0; s[i] != '\0'; ++i ) { // 此处就是将 二十六个小写字母转化成 nc进制
if( !toInt[s[i]] )
toInt[s[i]] = ++cnt;
if ( cnt == nc ) break;
}
rg int ans = 0;
rg int len = strlen(s)-n;
for ( rg int i = 0; i <= len; ++i ) {
rg int sum = 0;
for( rg int j = 0; j < n; ++j )
sum = sum*nc+toInt[s[i+j]]-1; // n进制从零开始算的, 此时要减一, 这个公式太巧妙了
if( !hs[sum] )
hs[sum]=true,ans++;
}
pf( "%d\n", ans );
return 0;
}