hash查找//hash函数及建表
给定一个序列：abcd，从中间一处断开，然后两段可以自由组合。比如ab-cd 组合有：abcd,abdc,bacd,badc,cdab,cdba,dcab,dcba。类似这样。问有多少种组合。思路：hash来记录状态，模拟。
#include<iostream>#include<string>using namespace std;#define maxn 10000class node{public:string st;node * next;}*pp={NULL};int cnt;void ini(){for(int i=0;i<maxn;i++){pp=new node();//申请内存pp->next =NULL;//初始化}}int ha(string x){unsigned long h=0;int len=x.length (); int i=0;while(i<len){h=(h<<4)+(int)x.at (i++);unsigned long g=h&0xf0000000L;if(g) h^=g>>24;h&=~-g; }return h%maxn;}voidfind(string ch,int h){node * head=pp ;while(head!=NULL){if(head->st .compare (ch)==0) return ;head=head->next ;}cnt++;node *q=new node();q->st =ch;q->next =pp ;//插在表头pp=q;}void add(int u,int v,int len,string str){int i,j;string a,b,c,d;a.clear ();b.clear ();c.clear ();d.clear ();for(i=0;i<=u;i++){a+=str.at(i);b+=str.at(u-i);}for(i=v,j=0;i<len;i++){c+=str.at(i);d+=str.at(len-1-j);j++;}int h;h=ha(a+c);find(a+c,h);h=ha(a+d);find(a+d,h);h=ha(b+c);find(b+c,h);h=ha(b+d);find(b+d,h);h=ha(c+a);find(c+a,h);h=ha(d+a);find(d+a,h);h=ha(c+b);find(c+b,h);h=ha(d+b);find(d+b,h);}void solve(string str){ini();int len=str.length();cnt=0;for(int i=0;i<len-1;i++)add(i,i+1,len,str);cout<<cnt<<endl;}int main(){int test;cin>>test;string str;while(test--){str.clear ();cin>>str;solve(str);}return 0;}
页:
[1]