common_sub_str

[c++]代码库

#include<iostream>
#include<cstring>
#include<strings.h>
#include<vector>
using namespace std;

//int map[3000][3000];

const string lcs(const string& str1,const string& str2);
const vector<string> lcs_vt(const string &str1, const string &str2);
const vector<string> n_lcs(vector<string> &strs);
vector<string> split_with_string(const string& str, const string& delim);
int print_vt(vector<string> &vt);
int vector_unique(vector<string> &vt);

int main(int argc, char *argv[])
{
	//string lcs=lcs(argv[1],argv[2]);
	char buf[102400];
	vector<string> substr_vt;
	vector<string> strs;

	while(fgets(buf, 102400, stdin)) {
		if (buf[strlen(buf) - 1] == '\n') {
			buf[strlen(buf) - 1] = 0;
		}
		string temp = buf;
		strs.push_back(temp);
	}

	substr_vt = n_lcs(strs);
	vector_unique(substr_vt);
	cout << "-------------------------------" << endl;
	for(unsigned int i = 0; i < substr_vt.size(); i++) {
		cout << substr_vt[i] << endl;
	}
	cout << "-------------------------------" << endl;
	return 0;
}

const vector<string> n_lcs(vector<string> &strs)
{
	vector<string> substr_vt;
	vector<string> temp_substr_vt;
	substr_vt.push_back(strs[0]);

	for(unsigned int i = 1; i < strs.size(); i++) {
		fprintf(stderr, "strs.size:%d, substr_vt.size:%d\n", strs.size(), substr_vt.size());
		for(unsigned int j = 0; j < substr_vt.size(); j++) {
			vector<string> temp_vt;
			//fprintf(stderr, "befre lcs_vt\n");
			temp_vt = lcs_vt(substr_vt[j], strs[i]);
			//fprintf(stderr, "after lcs_vt\n");

			vector_unique(temp_vt);
			for(unsigned int k = 0; k < temp_vt.size(); k++) {
				temp_substr_vt.push_back(temp_vt[k]);
			}
		}
		vector_unique(temp_substr_vt);
		//print_vt(temp_substr_vt);
		substr_vt.clear();
		substr_vt = temp_substr_vt;
		temp_substr_vt.clear();
	}

	/*
	int max_length = 0;
	vector<int> max_index_vt;
	for(unsigned int i = 0; i < substr_vt.size(); i++) {
		if (substr_vt[i].length() > max_length) {
			max_length = substr_vt[i].length();
		}
	}
	temp_substr_vt.clear();
	for(unsigned int i = 0; i < substr_vt.size(); i++) {
		if (substr_vt[i].length() == max_length) {
			//max_index_vt.push_back(i);
			temp_substr_vt.push_back(substr_vt[i]);
		}
	}

	return temp_substr_vt;
	*/
	return substr_vt;
}

const vector<string> lcs_vt(const string &str1, const string &str2)
{
	int col_num = str1.length();
	int row_num = str2.length();
	int map[row_num][col_num];

	bzero(map, sizeof(map));
	vector<string> ret;

	for(int i = 0; i < col_num; i++) {
		for(int j = 0; j < row_num; j++) {
			if (str1[i] == str2[j]) {
				map[j][i] = 1;
			}
		}
	}

	int list_flag = 0;
	string temp;
	for (int i = col_num - 1; i >= 0; i--) {
		int j = 0;
		temp = "";
		while(j + i < col_num && j < row_num) {
			if (map[j][j + i] == 1) {
				temp += str1[j + i];
			} else {
				temp += '#';
			}
			j++;
		}
		//if (!(temp.empty())) {
		//	cout << "###" << temp << endl;
		//}
		vector<string> splited_str = split_with_string(temp, "#");
		vector_unique(splited_str);
		for(unsigned int i = 0; i < splited_str.size(); i++) {
			ret.push_back(splited_str[i]);
		}
	}

	for (int i = 1; i < row_num; i++) {
		int j = 0;
		temp = "";
		while(j < col_num && j + i < row_num) {
			if (map[j + i][j] == 1) {
				temp += str2[j + i];
			} else {
				temp += '#';
			}
			j++;
		}
		//if (!(temp.empty())) {
		//	cout << "###" << temp << endl;
		//}
		vector<string> splited_str = split_with_string(temp, "#");
		vector_unique(splited_str);
		for(unsigned int i = 0; i < splited_str.size(); i++) {
			ret.push_back(splited_str[i]);
		}
	}
	
	/*
	cout << "======================================" << endl;
	cout << " " << str1 << endl;
	for(int i = 0; i < row_num; i++) {
		cout << str2[i];
		for(int j = 0; j < col_num; j++) {
			cout << map[i][j];
		}
		cout << endl;
	}
	cout << "======================================" << endl;
	*/
	//cout << "======================================" << endl;
	vector_unique(ret);
	//print_vt(ret);
	//cout << "======================================" << endl;
	return ret;
}

const string lcs(const string& str1,const string& str2)
{
	int xlen=str1.size();       //横向长度
	vector<int> tmp(xlen);        //保存矩阵的上一行
	vector<int> arr(tmp);     //当前行
	int ylen=str2.size();       //纵向长度
	int maxele=0;               //矩阵元素中的最大值
	int pos=0;                  //矩阵元素最大值出现在第几列
	for(int i=0;i<ylen;i++){
		string s=str2.substr(i,1);
		arr.assign(xlen,0);     //数组清0
		for(int j=0;j<xlen;j++){
			if(str1.compare(j,1,s)==0){
				if(j==0)
					arr[j]=1;
				else
					arr[j]=tmp[j-1]+1;
				if(arr[j]>maxele){
					maxele=arr[j];
					pos=j;
				}
			}       
		}
		tmp.assign(arr.begin(),arr.end());
	}
	string res=str1.substr(pos-maxele+1,maxele);
	return res;
}

vector<string> split_with_string(const string& str, const string& delim)
{
	vector<string> substr_vt;
	int where_delim;
	int old_offset = 0;
	string temp;

	while((where_delim = str.find(delim, old_offset)) != string::npos) {
		temp.assign(str, old_offset, where_delim - old_offset);
		if (!(temp.empty())) { 
			substr_vt.push_back(temp);
		}
		old_offset = where_delim + delim.length();
		where_delim = old_offset;
	}
	temp.assign(str, old_offset, str.length() - old_offset);
	if (!(temp.empty())) {
		substr_vt.push_back(temp);
	}

	return substr_vt;
}

int print_vt(vector<string> &vt)
{
	cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
	for(unsigned int i = 0; i < vt.size(); i++) {
		cout << vt[i] << endl;
	}
	cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
}

int vector_unique(vector<string> &vt)
{
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
}