一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 624|回复: 3
收起左侧

[算法题] 一道找最长单词并且由其他单词组成的题

[复制链接] |试试Instant~ |关注本帖
Jaden 发表于 2015-2-7 06:59:20 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
各位大神,题目就是给你一个170k单词的文件,让你找里面最长和第二长的单词并且能由其他文件里的单词组成。下面是我写的程序,对于单词量不大的比如几百个的或者几十个的,都没问题。但是170k的一进来,我加红色的那块 根本就运行不了了,求大神帮忙,谢谢!

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <string>
#include <array>
#include <vector>
using namespace std;

bool compare (string a, string b) { return b.length()<a.length(); }

bool answer(int start, int len, string piece, unordered_set<string>& myset)
{
    if (start == len) return true;
   
    for (int i=start; i<len; i++)
    {
        string sub = piece.substr(start, i-start+1);
        //cout << "sub = "<<sub << endl;
        if (sub == piece) {
            return false;
        }
        if (myset.find(sub) != myset.end())
        {
            cout << "find sub = " << sub << endl;
            if (answer(i+1,len,piece,myset))  return true;
        }

    }
    return false;
}

int main()
{
    /*unordered_set<string> myset = { "a", "able", "about", "account", "acid", "across",
        "act", "addition", "adjustment", "advertisement", "after",
        "again", "against", "agreement", "air", "all", "almost",
        "among", "amount", "amusement", "and", "angle", "angry",
        "animal", "answer", "ant", "any", "apparatus", "apple",
        "approval", "arch", "argument", "arm", "army", "art", "as",
        "at", "attack", "attempt", "attention", "attraction",
        "authority", "automatic", "awake", "baby", "back", "bad",
        "bag", "balance", "ball", "band", "base", "basin", "basket",
        "bath", "be", "beautiful", "because", "bed", "bee", "before",
        "behaviour", "belief", "bell", "bent", "berry", "between",
        "bird", "birth", "bit", "bite", "bitter", "black", "blade",
        "blood", "blow", "blue", "board", "boat", "body", "boiling",
        "bone", "book", "boot", "bottle", "box", "boy", "brain",
        "brake", "branch", "brass", "bread", "breath", "brick",
        "bridge", "bright", "broken", "brother", "brown", "brush",
        "bucket", "building", "bulb", "burn", "burst", "business",
        "but", "butter", "button", "by", "cake", "camera", "canvas",
        "card", "care", "carriage", "cart", "cat", "cause", "certain",
        "chain", "chalk", "chance", "change", "cheap", "cheese",
        "chemical", "chest", "chief", "chin", "church", "circle",
        "clean", "clear", "clock", "cloth", "cloud", "coal", "coat",
        "cold", "collar", "colour", "comb", "come", "comfort",
        "committee", "common", "company", "comparison", "competition",
        "complete", "complex", "condition", "connection", "conscious",
        "control", "cook", "copper", "copy", "cord", "cork", "cotton",
        "cough", "country", "cover", "cow", "crack", "credit", "crime",
        "cruel", "crush", "cry", "cup", "cup", "current", "curtain",
        "curve", "cushion", "damage", "danger", "dark", "daughter",
        "day", "dead", "dear", "death", "debt", "decision", "deep",
        "degree", "delicate", "dependent", "design", "desire",
        "destruction", "detail", "development", "different",
        "digestion", "direction", "dirty", "discovery", "discussion",
        "disease", "disgust", "distance", "distribution", "division",
        "do", "dog", "door", "doubt", "down", "drain", "drawer",
        "dress", "drink", "driving", "drop", "dry", "dust", "ear",
        "early", "earth", "east", "edge", "education", "effect", "egg",
        "elastic", "electric", "end", "engine", "enough", "equal",
        "error", "even", "event", "ever", "every", "example",
        "exchange", "existence", "expansion", "experience", "expert",
        "eye", "face", "fact", "fall", "FALSE", "family", "far",
        "farm", "fat", "father", "fear", "feather", "feeble",
        "feeling", "female", "fertile", "fiction", "field", "fight",
        "finger", "fire", "first", "fish", "fixed", "flag", "flame",
        "flat", "flight", "floor", "flower", "fly", "fold", "food",
        "foolish", "foot", "for", "force", "fork", "form", "forward",
        "fowl", "frame", "free", "frequent", "friend", "from", "front",
        "fruit", "full", "future", "garden", "general", "get", "girl",
        "give", "glass", "glove", "go", "goat", "gold", "good",
        "government", "grain", "grass", "great", "green", "grey",
        "grip", "group", "growth", "guide", "gun", "hair", "hammer",
        "hand", "hanging", "happy", "harbour", "hard", "harmony",
        "hat", "hate", "have", "he", "head", "healthy", "hear",
        "hearing", "heart", "heat", "help", "high", "history", "hole",
        "hollow", "hook", "hope", "horn", "horse", "hospital", "hour",
        "house", "how", "humour", "I", "ice", "idea", "if", "ill",
        "important", "impulse", "in", "increase", "industry", "ink",
        "insect", "instrument", "insurance", "interest", "invention",
        "iron", "island", "jelly", "jewel", "join", "journey", "judge",
        "jump", "keep", "kettle", "key", "kick", "kind", "kiss",
        "knee", "knife", "knot", "knowledge", "land", "language",
        "last", "late", "laugh", "law", "lead", "leaf", "learning",
        "leather", "left", "leg", "let", "letter", "level", "library",
        "lift", "light", "like", "limit", "line", "linen", "lip",
        "liquid", "list", "little", "living", "lock", "long", "look",
        "loose", "loss", "loud", "love", "low", "machine", "make",
        "male", "man", "manager", "map", "mark", "market", "married",
        "mass", "match", "material", "may", "meal", "measure", "meat",
        "medical", "meeting", "memory", "metal", "middle", "military",
        "milk", "mind", "mine", "minute", "mist", "mixed", "money",
        "monkey", "month", "moon", "morning", "mother", "motion",
        "mountain", "mouth", "move", "much", "muscle", "music", "nail",
        "name", "narrow", "nation", "natural", "near", "necessary",
        "neck", "need", "needle", "nerve", "net", "new", "news",
        "night", "no", "noise", "normal", "north", "nose", "not",
        "note", "now", "number", "nut", "observation", "of", "off",
        "offer", "office", "oil", "old", "on", "only", "open",
        "operation", "opinion", "opposite", "or", "orange", "order",
        "organization", "ornament", "other", "out", "oven", "over",
        "owner", "page", "pain", "paint", "paper", "parallel",
        "parcel", "part", "past", "paste", "payment", "peace", "pen",
        "pencil", "person", "physical", "picture", "pig", "pin",
        "pipe", "place", "plane", "plant", "plate", "play", "please",
        "pleasure", "plough", "pocket", "point", "poison", "polish",
        "political", "poor", "porter", "position", "possible", "pot",
        "potato", "powder", "power", "present", "price", "print",
        "prison", "private", "probable", "process", "produce",
        "profit", "property", "prose", "protest", "public", "pull",
        "pump", "punishment", "purpose", "push", "put", "quality",
        "question", "quick", "quiet", "quite", "rail", "rain", "range",
        "rat", "rate", "ray", "reaction", "reading", "ready", "reason",
        "receipt", "record", "red", "regret", "regular", "relation",
        "religion", "representative", "request", "respect",
        "responsible", "rest", "reward", "rhythm", "rice", "right",
        "ring", "river", "road", "rod", "roll", "roof", "room", "root",
        "rough", "round", "rub", "rule", "run", "sad", "safe", "sail",
        "salt", "same", "sand", "say", "scale", "school", "science",
        "scissors", "screw", "sea", "seat", "second", "secret",
        "secretary", "see", "seed", "seem", "selection", "self",
        "send", "sense", "separate", "serious", "servant", "sex",
        "shade", "shake", "shame", "sharp", "sheep", "shelf", "ship",
        "shirt", "shock", "shoe", "short", "shut", "side", "sign",
        "silk", "silver", "simple", "sister", "size", "skin", "skirt",
        "sky", "sleep", "slip", "slope", "slow", "small", "smash",
        "smell", "smile", "smoke", "smooth", "snake", "sneeze", "snow",
        "so", "soap", "society", "sock", "soft", "solid", "some", "",
        "son", "song", "sort", "sound", "soup", "south", "space",
        "spade", "special", "sponge", "spoon", "spring", "square",
        "stage", "stamp", "star", "start", "statement", "station",
        "steam", "steel", "stem", "step", "stick", "sticky", "stiff",
        "still", "stitch", "stocking", "stomach", "stone", "stop",
        "store", "story", "straight", "strange", "street", "stretch",
        "strong", "structure", "substance", "such", "sudden", "sugar",
        "suggestion", "summer", "sun", "support", "surprise", "sweet",
        "swim", "system", "table", "tail", "take", "talk", "tall",
        "taste", "tax", "teaching", "tendency", "test", "than", "that",
        "the", "then", "theory", "there", "thick", "thin", "thing",
        "this", "thought", "thread", "throat", "through", "through",
        "thumb", "thunder", "ticket", "tight", "till", "time", "tin",
        "tired", "to", "toe", "together", "tomorrow", "tongue",
        "tooth", "top", "touch", "town", "trade", "train", "transport",
        "tray", "tree", "trick", "trouble", "trousers", "TRUE", "turn",
        "twist", "umbrella", "under", "unit", "up", "use", "value",
        "verse", "very", "vessel", "view", "violent", "voice",
        "waiting", "walk", "wall", "war", "warm", "wash", "waste",
        "watch", "water", "wave", "wax", "way", "weather", "week",
        "weight", "well", "west", "wet", "wheel", "when", "where",
        "while", "whip", "whistle", "white", "who", "why", "wide",
        "will", "wind", "window", "wine", "wing", "winter", "wire",
        "wise", "with", "woman", "wood", "wool", "word", "work",
        "worm", "wound", "writing", "wrong", "year", "yellow", "yes",
        "yesterday", "you", "young" };*/
   
   
    /*unordered_set<string> myset ={"test", "tester", "testertest", "testing",
        "apple", "seattle", "banana",  "batting", "ngcat",
        "batti","bat", "testingtester", "testbattingcat"};*/
   
    unordered_set<string> myset;
    ifstream myfile("wordsforproblem.txt");
    string line;
    if (myfile.is_open())
    {
        while ( getline (myfile,line) )
        {
            myset.insert(line);
        }
        myfile.close();
    }
   

    vector<string> base(myset.begin(), myset.end());
    sort(base.begin(), base.end(),compare);
    for (int i=0;i<myset.size(); i++) {
        cout << base<<endl;
    }
    vector<string> results;
    int count = 0;
    string first, second;
    for (int i=0;i<myset.size();i++)
    {
        int len = base.length();
        if (answer(0,len,base,myset))
        {
            count++;
            if (count == 1) first = base;
            if (count == 2) second = base;
        }
        //cout <<"------------------------------------------------------"<<endl;
    }
   
    cout << first << endl << second << endl << count << endl;
    return 0;
}





miss_snow 发表于 2015-2-7 07:33:17 | 显示全部楼层
字符串题目吧~具体没做过,但感觉会不会是自动机或者后缀树之类的?
回复 支持 反对

使用道具 举报

 楼主| Jaden 发表于 2015-2-7 10:35:59 | 显示全部楼层
miss_snow 发表于 2015-2-7 07:33
字符串题目吧~具体没做过,但感觉会不会是自动机或者后缀树之类的?

我觉得算法应该是对的,可能需要一些优化?就是当文件不大的时候,比如几十个单词,是完全正确的。但是文件一大,if (myset.find(sub) != myset.end()) 根本就一次也过不了,我也不明白什么原因。
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-2-7 20:41:11 | 显示全部楼层
Jaden 发表于 2015-2-7 10:35
我觉得算法应该是对的,可能需要一些优化?就是当文件不大的时候,比如几十个单词,是完全正确的。但是文 ...

对的,太朴素了,还是要用字符串做一下吧~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 03:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表