用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c++代码库

common_sub_str

2013-08-27 作者： kelly举报

[c++]代码库

view sourceprint?
#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());
}


网友评论    (发表评论)

共1 条评论 1/1页

发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...