给定一个字符串数组,将所有字符串分组,每一组的字符串包含的字符相同但是顺序不同。
如:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include "mpi.h"
#define ROOT_PROCESS 0
using namespace std;
vector<string> all_content;
unordered_map<string, vector<string>> grouped_strings;
unordered_map<size_t, size_t> length_counts;
void read_all(ifstream& file) {
string line;
while (getline(file, line)) {
if (!line.empty() && line.back() == 13)
line.pop_back();
all_content.push_back(line);
string sorted_line = line;
sort(sorted_line.begin(), sorted_line.end());
grouped_strings[sorted_line].push_back(line);
length_counts[line.size()] += 1;
}
}
void print() {
if (grouped_strings.empty()) return;
cout << "[" << endl;
for (auto it = grouped_strings.begin(); it != grouped_strings.end(); ++it) {
cout << " [";
for (const auto& str : it->second) {
cout << str << ",";
}
cout << "]" << endl;
}
cout << "]" << endl;
for (const auto& pair : length_counts) {
cout << pair.first << ": " << pair.second << endl;
}
}
int main(int argc, char* argv[]) {
MPI_Init(&argc, &argv);
int num_procs, my_rank;
MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
if (argc != 2) {
if (my_rank == ROOT_PROCESS)
cerr << "Usage: " << argv[0] << " <filename>" << endl;
MPI_Finalize();
return 1;
}
ifstream file(argv[1]);
if (!file.is_open()) {
if (my_rank == ROOT_PROCESS)
cerr << "Error opening file" << endl;
MPI_Finalize();
return 1;
}
if (my_rank == ROOT_PROCESS) {
read_all(file);
file.close();
}
// Broadcast data to all processes
// Assume all_content, grouped_strings, and length_counts are filled on ROOT_PROCESS
MPI_Bcast(&all_content[0], all_content.size(), MPI_CHAR, ROOT_PROCESS, MPI_COMM_WORLD);
// Determine portion of work for each process
int portion_size = all_content.size() / num_procs;
int start = my_rank * portion_size;
int end = (my_rank + 1) * portion_size;
// Each process works on its portion of data
for (int i = start; i < end; ++i) {
string line = all_content[i];
string sorted_line = line;
sort(sorted_line.begin(), sorted_line.end());
grouped_strings[sorted_line].push_back(line);
length_counts[line.size()] += 1;
}
// Gather results to ROOT_PROCESS for printing
MPI_Barrier(MPI_COMM_WORLD);
if (my_rank == ROOT_PROCESS) {
print();
}
MPI_Finalize();
return 0;
}