首页 > 代码库 > 字符串排列后匹配
字符串排列后匹配
这题 我是在待字闺中看到的 他介绍了一种使用快排排序后 不断进行匹配的算法
这边 我用了下map来做 直接用hash数组也可以
我觉得 用hash数组的话 存 删都是O(1)完成 map则是log(n)
但是使用hash遍历会需要遍历很多无效字符 而map则使用迭代器 方便很多
两者各有优劣吧... 、
原题 贴下
给定两个字符串A和B，判断A中是否包含由B中字符重新排列成的新字符串。例如：A=abcdef, B=ba，结果应该返回true。因为ba的排列ab，是A的子串。
1 #include <iostream> 2 #include <map> 3 using namespace std; 4 5 map<char,int>mp_model; 6 map<char,int>mp_goal; 7 map<char,int>::iterator it_goal; 8 map<char,int>::iterator it_model; 9 const int size = 1010;10 char model[size];11 char goal[size];12 13 bool judge( )14 {15 for( it_model = mp_model.begin() , it_goal = mp_goal.begin() ; it_model!=mp_model.end()&& it_goal!=mp_goal.end() ; it_model++ , it_goal++ )16 {17 if( it_model->first != it_goal->first || it_model->second!= it_goal->second )18 return false;19 }20 if( it_model != mp_model.end() || it_goal != mp_goal.end() )21 return false;22 return true;23 }24 25 int main()26 {27 bool flag;28 int len_model , len_goal;29 while( cin >> model >> goal )30 {31 mp_model.clear();32 mp_goal.clear();33 flag = false;34 len_model = strlen(model);35 len_goal = strlen(goal);36 if( len_model < len_goal )37 {38 cout << "False" << endl;39 }40 else41 {42 for( int i = 0 ; i<len_goal ; i++ )43 {44 mp_goal[ goal[i] ] ++;45 mp_model[ model[i] ] ++;46 }47 for( int j = len_goal-1 ; j<len_model ; j++ )48 {49 flag = judge( );50 if( flag )51 {52 break;53 }54 else55 {56 mp_model[ j+1-len_goal] --;57 mp_goal[j] ++;58 }59 }60 if(flag)61 cout << "True" << endl;62 else63 cout << "False" << endl;64 }65 }66 return 0;67 }
today:
我大二了
轮到我去招新了
时间过得好快
学弟学妹是否会如我当初一样呢
要做点题目了 不然很丢人那
字符串排列后匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。