首页 > 代码库 > poj 1200 Crazy Search
poj 1200 Crazy Search
题目:
链接:点击打开链接
题意:
输入n和nc,以及字符串s,输出长度为n的不同字串的个数。
算法:
思路:
用hash判重(hash值。。。。。。),看了大牛的代码,对hash还是不甚理解。。。。
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<cstdio> using namespace std; #define MAXN 16000010 const int MAXN1 = 257; int hash[MAXN]; int m[MAXN1]; char s[1000000]; int main() { freopen("input.txt","r",stdin); int n,nc; int sum = 0,sum1 = 0,sum2 = 0; memset(hash,0,sizeof(hash)); memset(m,0,sizeof(m)); memset(s,0,sizeof(s)); scanf("%d%d",&n,&nc); getchar(); scanf("%s",s); int len = strlen(s); for(int i=0; i<len; i++) { if(!m[s[i]])//将每个字符赋值为相应ASCII的数 { m[s[i]] = ++sum; } if(sum == nc) { break; } } for(int i=0; i<=len-n; i++) { sum1 = 0; for(int j=0; j<n; j++)//将长度为n的子串变为一个nc进制的整数 { sum1 = sum1*nc + m[s[i+j]]-1; } if(!hash[sum1])//如果hash[sum1]==0表示没有没有出现过 { hash[sum1] = 1;//标记 ++sum2;//不同串的个数加1 } } printf("%d\n",sum2); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。