getting single characters from a string

[avarionist]

Im working on a program to get single characters from a string and i guess im doing it wrong but i was using strok() to tokenize the string in the hopes that it would do so but anyway this is what ive got so far
and before you ask its not for a college class i mean for goodness sakes im not even out of high yet.
now i know that im not using a delimiter so i understand if you post something about strok() but i guess what im asking is how would i go about obtaining a single char from a string or should i just use a char array? then call it by name ie ar[1]
the end goal however is to take all the characters in a string and see what words you can make out of it(compared against data in a file).

//for example
FILE:
rabbit ball
at all new found etc.

input:cat
at found

#include <iostream>
#include <string>
using namespace std;

int main(){
    char input[30];
    char * sc;
    cout<<"Name:";
    cin>>input;
    pch= strtok(input, "");
    while(sc != NULL){
        cout<<sc<<endl;
        pch=strtok(NULL,"");
    }
}

[mrnutty]

>>how would i go about obtaining a single char from a string

Huh, I'm confused on what you want, you do know you can use string.operator[] to
access the individual characters right?

string str = "text";
char ch = str[0]; //ch equals 't'
char ch2 = str[ str.size()-1]; //ch2 equals 't';

[NathanOliver]

I think what you are trying to do is input a word and see if any part of that word matches what you have in a text file. now do you want only sequential letters to make the work or can it be any combination of letters in the inputted word?
Example:
sequential search
"individual" has "in", "divi" and "dual"

or any combination
"individual" has "in", "dual" , "dial", "dan" and "lad"

If you only want sequential letters to make words then you are going to need three loops to accomplish this. The first to control where in the string to start from. The second loop will start from there and go on to the end of the string getting sub strings along the way. The third loop would go through the words in the file and see if the sub string matches any of the strings in the file. At least this is how I would go about.

If you want any combination of letters in the inputted word let us know and we can give you a hand thinking it through. Unless my first assumption was wrong and none of this applies.

[avarionist]

the latter it will test the letters against words that are defined in a file.

ie.

input:mister

words in input: mist is tier sim mise time trim etc.

so any combination of words

like
input:ready
output: read day year a; are found

[griswolf]

To restate the problem: Given a word as input, find all "legal" words that can be made by selecting letters from that word in any order, where "legal" words are those defined in a file.

As an example, if the file contains words "a", "bear", "bee", "cat", "have" then given input "behave" you would expect output "bee", "have", "a" (or some other order).

So you will want to populate a collection of the words in the file, and you will need to permute/combine the characters in the input, then compare each of those with the collection.

Is that right?

[avarionist]

right on the spot mate :p

[avarionist]

comparing the word to whats in the file isnt the hard part the hard part is splitting the characters from the given string into single chars then placing them next to each other in order to compare them so im assuming i would need 3 or 4 loops

[griswolf]

You can go at it from two directions: Either start by picking some combination of characters (one at a time for all of them) and then all the permutations, or some permutation of the word (one at a time for all of them) and then all the combinations.

One of the things to realize is the size of the combinatorial explosion as the length of the input increases.

You can treat a C type string (const) char * or a std::string as an array (operator[]).

Think about generating combinations of indices in the range (0,length(input)), then creating strings by extracting the characters at those indices, in order.

[NathanOliver]

I had a go at that last night and it can take a long time using words of a longer length. The number of possible permutation is string length!

http://www.daniweb.com/code/snippet217104.html

[griswolf]

I had a go at that last night and it can take a long time using words of a longer length. The number of possible permutation is string length!

It is bigger than that: For each permutation there are N possible prefixes of the string so the full cost is O(N * N!). You don't need to consider all substrings because each non-prefix substring would be the prefix of some other permutation. (PS it took me three times reading your post to recognize the final '!' as 'factorial'.

[avarionist]

thanks guys i kinda got an idea now though iamthwee in the

char alphabet={"-abcdefghijklmnopqrstuvwxyz"};

what is the - for ? (not code jacking btw copy paste just blows you dont learn poop from doing it) just curious ive seen it time and time again but never understood why people put the - at the beginning of the array ????
i also didnt know you could call an array through a value like iamthwee did. :)

@avarionist

I'm glad you got an idea through my code. The snippet should in fact do EVERYTHING you want, but if you want to just take bits from it that is OK.

The '-' sign at the beginning of the array isn't really necessary, in fact it could be any character literal. The only reason why I put it there was because I was iterating through the for loops starting at '1' instead of '0.' Why? I couldn't tell you because I wrote that some time ago.

In regards to the advice from other guys in this thread, you do NOT even have to consider creating a permute function or variations thereof. Unfortunately, they may have not seen the elegant solution which lies in a letter frequency counter, but that's OK.

A letter frequency counter solution is ideal because there is no real cost spent computing variations. It simply reads in an entire dictionary file just once and spits out the solution. So the time it takes is simply the time it takes to read the dictionary file... This is a hell of a lot faster, especially as any permutation solution run into exponential time real FCKING fast!

You can also optimize my algorithm, by grouping all the words in the dictionary file by length, and then do a look up by just length. This will cut down the times and will omit checking any words in the file that are greater than word.length().

Good luck.

[griswolf]

Rule one of optimizing: Find a better algorithm.

I'm still chewing on iamthewee's code, which I think I've almost got a handle on, but it does appear to do what's needed.

[Bench]

Rule one of optimizing: Find a better algorithm.

I disagree there. Rule one of optimising: DON'T!

at least, not until you have a working program which has been thoroughly tested and the result of that testing has shown that it actually needs optimising; at which point, careful analysis needs to be done to make sure that the bits which are being examined for optimisation are actually the bits which are causing problems in the first place.

[griswolf]

Agree. I was using a zero based rule system ;)

[NathanOliver]

Sorry about the bad syntax with string length!. I should of written as (string length)!.

[avarionist]

Again thanks guys :)
I'm glad that there was some interest in this thread hopefully someone else will find it useful.
ill post all my code when i get done with it
ok :)

[NathanOliver]

Well I came up with a solution for this that I thinks works like iamthewee's code but I'm not sure. It will run through all the words supplied to the function in the vector against the string supplied to the function. It got away from me a little bit and is a little more complex than I thought it would be but it works for what I have tried.

#include <string>
#include <vector>
#include <set>

std::vector<std::string> AnyWordFinder(const std::string & input, const std::vector<std::string> & wordList)
{
    std::vector<std::string> foundWords;
    std::set<int> foundCharacters;
    std::vector<std::string>::const_iterator it = wordList.begin(), end = wordList.end();
    std::string temp;
    while (it != end)
    {
        size_t size = (*it).size();
        size_t pos = 0;
        if (size > input.size())
        {
            it++;
            continue;
        }
        for (size_t i = 0; i < size; i++)
        {
            pos = input.find_first_of((*it)[i], 0);
            if (pos == std::string::npos)
                break;
            if (foundCharacters.insert(pos).second != true)
            {
                // this sees if there are any more (*it)[i]'s in the input string
                while ((pos = input.find_first_of((*it)[i], pos + 1)) != std::string::npos)
                {
                    if (foundCharacters.insert(pos).second == true)
                        break;
                }
                if (pos == std::string::npos)
                    break;
            }
            temp += (*it)[i];
        }
        if (temp == *it)
            foundWords.push_back(temp);
        foundCharacters.clear();
        temp.clear();
        it++;
    }
    return foundWords;
}

Post an example of a driver function using int main And I'll run a few tests against my algorithm which I know to be 100% correct.

[NathanOliver]

@ iamthwee
Here is the driver I used to test my function. The little dictionary file I made is also attached. The function was in a header called WordFinder.h and this is my Main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include "WordFinder.h"

using namespace std;

int main()
{
    string word = "individual", temp;
    vector<string> wordList;
    vector<string> foundWords;
    ifstream fin("dictionary.txt");
    if (fin.fail())
    {
        cout << "Unable to open file!";
        cin.get();
        return 0;
    }
    while (getline(fin, temp))
        wordList.push_back(temp);
    foundWords = AnyWordFinder(word, wordList);
    size_t size = foundWords.size();
    for (size_t i = 0; i < size; i ++)
    {
        cout << foundWords[i] << " found\n";
    }
    cin.get();
    return 0;
}

Looks good to me.

All tests have passed.

[NathanOliver]

Thanks iamthwee