【算法】频繁集（字符串技巧，多种容器混合，map嵌套vector）

向右看齐 2022-09-15 05:37 9阅读 0赞

## 本题问题来源于Apriori算法的其中一个步骤 ##

题目直接复制会乱码  
![在这里插入图片描述][09eb7eaed6b54f57baa7665b16a0a544.png_x-oss-process_image]  
![在这里插入图片描述][5944fb769e954c08b92f6b399a925ffa.png_x-oss-process_image]

**题意：**  
将头相同（头的长度为k-1，不包括最后一个字符）长度为k的字符串组合成长度为k+1的新字符串，新字符串尾巴长度为2，由找出的字符串尾巴按字典序序排列而成。  
注意：最后输出的字符串序列也是有序的。

**输入样例：**  
5 2  
ac  
bc  
ad  
be  
ce  
**输出样例：**  
2  
acd  
bce

## 1、O(n^2)暴力比较 ##

vector当容器

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main()
    {
        
    	int n,k;
    	while(scanf("%d %d",&n,&k)!=EOF) {
         //多组输入输出，这题没用到就是了 
    		string str[n];
    		vector<string> ans;
    		for(int i=0; i<n; i++) {
        
    			cin>>str[i];
    		}
    		for(int i=0; i<n; i++) {
        
    			for(int j=i+1; j<n; j++) {
        
    				//if(str[i].compare(0,k-1,str[j],0,k-1)==0) { //比较头是否相同，方法有很多 
    				if(str[i].substr(0,k-1) == str[j].substr(0,k-1)) {
        
    					if(str[i][k-1]<str[j][k-1])
    						ans.push_back(str[i]+str[j][k-1]);
    					else
    						ans.push_back(str[j]+str[i][k-1]);
    				}
    			}
    		}
    		sort(ans.begin(),ans.end());  //最后结果不排序，只有1分，满分10分 
    		cout<<ans.size()<<endl;
    		for(int i=0; i<ans.size(); i++) {
        
    			cout<<ans[i]<<endl;
    		}
    	}
    	return 0;
    }

set当容器

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	int n,k;
    	scanf("%d %d",&n,&k);
    	string str[n];
    	set<string> ans;
    	for(int i=0; i<n; i++) {
        
    		cin>>str[i];
    	}
    	for(int i=0; i<n; i++) {
        
    		for(int j=i+1; j<n; j++) {
        
    			if(str[i].compare(0,k-1,str[j],0,k-1)==0) {
        
    				if(str[i][k-1]<str[j][k-1])
    					ans.insert(str[i]+str[j][k-1]);
    				else
    					ans.insert(str[j]+str[i][k-1]);
    			}
    		}
    	}
    	cout<<ans.size()<<endl;
    	for(set<string>::iterator it = ans.begin(); it != ans.end(); it++) {
        
    		cout<<*it<<endl;
    	}
    	return 0;
    }

## 2、map嵌套vector记数据，set存答案,排序都省了 ##

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	int n,k;   
    	cin>>n>>k;
    	map<string,vector<char> > fre;
    	set<string> ans;
    	for(int i=0; i<n; i++) {
        
    		string str,tmp;
    		cin>>str;
    		tmp = str.substr(0,k-1);
    		if(fre.count(tmp)>0) {
         //tmp出现返回1，未出现返回0 
    			vector<char> t = fre.find(tmp)->second; 
    			//迭代器遍历map的第二个元素vector容器 
    			for (vector<char>::iterator inner = t.begin(); inner != t.end(); ++inner) {
        
    				if(*inner < str[k-1])
    					ans.insert(tmp+*inner+str[k-1]);
    				else
    					ans.insert(tmp+str[k-1]+*inner);
    			}
    			fre.find(tmp)->second.push_back(str[k-1]);
    		} else {
        
    			fre[tmp].push_back(str[k-1]);
    		}
    	}
    	cout<<ans.size()<<endl; 
    	//这里是迭代器遍历set容器，现在auto比较流行，但不一定编译器支持 
    	for(set<string>::iterator it = ans.begin(); it != ans.end(); it++) {
        
    		cout<<*it<<endl;
    	}
    	return 0;
    }

unordered\_map提高性能（存数据不需要有序）  
auto 遍历增加可读性，更简洁！

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	int n,k;
    	cin>>n>>k;
    	unordered_map<string,vector<char> > fre;
    	set<string> ans;
    	for(int i=0; i<n; i++) {
        
    		string str,tmp;
    		cin>>str;
    		tmp = str.substr(0,k-1);
    		if(fre.count(tmp)>0) {
        
    			for (auto inner:fre.find(tmp)->second) {
        
    				if(inner < str[k-1])
    					ans.insert(tmp+inner+str[k-1]);
    				else
    					ans.insert(tmp+str[k-1]+inner);
    			}
    			fre.find(tmp)->second.push_back(str[k-1]);
    		} else {
        
    			fre[tmp].push_back(str[k-1]);
    		}
    	}
    	cout<<ans.size()<<endl;
    	for(auto it:ans) {
        
    		cout<<it<<endl;
    	}
    	return 0;
    }

## 部分测试数据 ##

7 3
    bbx
    bbc
    bba
    aaz 
    aax
    bbe
    abc
    
    7
    aaxz
    bbac
    bbae
    bbax
    bbce
    bbcx
    bbex

6 2
    ce
    be
    ad
    bc
    ac
    ab
    
    4
    abc
    abd
    acd
    bce

[09eb7eaed6b54f57baa7665b16a0a544.png_x-oss-process_image]: /images/20220828/5ecdca0dd8e740abb40c823f66f60724.png
[5944fb769e954c08b92f6b399a925ffa.png_x-oss-process_image]: /images/20220828/2011cd28d554434f94f0c9ba19c3f27f.png