首页 > 代码库 > 怎样迅速匹配兄弟字符串
怎样迅速匹配兄弟字符串
假设两个字符串的字符一样,可是顺序不一样,被觉得是兄弟字符串。问怎样在迅速匹配兄弟字符串(如,bad和adb就是兄弟字符串)。思路:推断各自素数乘积是否相等。
1、推断两个字符串的长度是否一样。
2、每一个字符串按字符排序。如acb排序之后是abc,假设是兄弟字符串的话,排序之后是一样的。
给26个字符依次赋予质数。质数是比較特殊的一堆数字,它们仅仅能被1和本身整除。
给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13 等等……
加法:两个字符串中的全部字符都赋值了,接着让它们各自相加。假设两个字符串得出的结果是一样的,那它们是兄弟字符串。
可是,b+f=3+13=16。c+e=5+11=16,所以有误。
乘法:两个字符串中的全部字符让它们各自相乘。方法是对的,可是会溢出。所以要大整数处理了。
用平方和或者立方和:考虑平方和会不会解决加法有误。乘法溢出:b*b+f*f=3*3+13*13=178;c*c+e*e=5*5+11*11=146;
用hashmap能够。以字母为key。出现的次数为value,次数一样即为同样的。
方法三代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; int main() { int hash1[256],hash2[256],i,len1,len2; char str1[100],str2[100]; printf("请输入2个字符串:(0结束)\n"); while(1) { //输入 scanf("%s",str1); if(!strcmp(str1,"0")) break; scanf("%s",str2); //比較长度 len1=strlen(str1); len2=strlen(str2); if(len1!=len2) { printf("%s,%s,二者不是兄弟字符串\n",str1,str2); continue; } //字符是否同样 memset(hash1,0,sizeof(hash1)); memset(hash2,0,sizeof(hash2)); for(i=0;i<len1;i++) { hash1[str1[i]]++; hash2[str2[i]]++; } for(i=0;i<255;i++) { if(hash1[i]!=hash2[i])//不同 break; } if(i==255) printf("%s,%s,二者是兄弟字符串\n",str1,str2); else printf("%s,%s,二者不是兄弟字符串\n",str1,str2); } } /* bad abd abcd abc aabbccdd abcdabcd abcdabc aabbccc aaa bbb ababa babab ababa aabba 0 */
怎样迅速匹配兄弟字符串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。