Thread: how to find the longest meaning substring?

I learned C abt 4 years ago, and havn't touched it since then. Recently, I need to program in C to find the longest meaning substring of a string without white space, given a sorted dictionary text file.

For example, I've a string "europeaninvestmentbank", I first want to identify "european" "investment" "bank", among other possible meaningful substrings, and then find the length of longest meaningful substring is 10 for "investment".

Is there any existing solutions in C?
Or I need to implement from scratch?

Thanks a million!

I always start with the easiest solution because I am not very smart. The easiest solution is strstr() on the whole search string starting with the longest string from the dictionary:

Code:

char** sorted_dict = dictionary_by_length();

while (sorted_dict)
{
    if (strstr(source, *sorted_dict))
    {
        printf("Longest meaningful substring: '%s'\n", *sorted_dict);
        break;
    }
}

dictionary_by_length() is a placeholder for whatever method you use to get the dictionary strings from longest to shortest.

Thanks very much Inanna, I think you are pointing me to the right direction. strstr() is indeed handy.

I'm not sure about using strstr directly as "strstr(source, *sorted_dict)", as it would return only the occurrence of complete "source" in dictionary, and what I want is the substrings of source.

As in the previous example, in the case of "europeaninvestmentbank" as source, I want to spot substring "investment" as the longest meaningful substring...

I'm trying to compare each word in my dictionary with every possible substring of my source, smartly (pfffff, don't know how exactly yet), with strstr(substring, word).

And currently got stuck at the very first step: while importing dictionary text into a 2d array of char. realloc() gave invalid next size error from now and then! No clue what's happening.

Originally Posted by Inanna

I always start with the easiest solution because I am not very smart. The easiest solution is strstr() on the whole search string starting with the longest string from the dictionary:

Code:

char** sorted_dict = dictionary_by_length();

while (sorted_dict)
{
    if (strstr(source, *sorted_dict))
    {
        printf("Longest meaningful substring: '%s'\n", *sorted_dict);
        break;
    }
}

dictionary_by_length() is a placeholder for whatever method you use to get the dictionary strings from longest to shortest.

I'm not sure about using strstr directly as "strstr(source, *sorted_dict)", as it would return only the occurrence of complete "source" in dictionary, and what I want is the substrings of source.

strstr("europeaninvestmentbank", "investment") will return &"europeaninvestmentbank"[8] because that is where the substring was found. It will return NULL if the substring was not found. Assuming you have the complete source string in memory and only search for the longest substrings first, strstr() will do what you are asking for.

Code:

#include <stdio.h>
#include <string.h>

// Ordered by length of the string
char const* dictionary[] =
{
    "investment",
    "european",
    "bank",
    NULL
};

int main()
{
    char const* source = "europeaninvestmentbank";
    char const** sorted_dict = dictionary;

    while (sorted_dict)
    {
        if (strstr(source, *sorted_dict))
        {
            printf("Longest meaningful substring: '%s'\n", *sorted_dict);
            break;
        }

        ++sorted_dict;
    }
}

And currently got stuck at the very first step: while importing dictionary text into a 2d array of char. realloc() gave invalid next size error from now and then! No clue what's happening.

Any kind of buffer overflow on a pointer to heap memory can mess up the heap and cause weird errors. Try this code on your dictionary file and see if the same thing happens:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TEST

int length_order(void const* lhs, void const* rhs);

int main()
{
    FILE* fp = fopen("test.txt", "r");
    char** dictionary = NULL;
    char word[1024];
    size_t size = 0;

    // Populate the dictionary
    while (fscanf(fp, "%1023s", word) == 1)
    {
        // Grow dictionary by 1 each time and assume allocations succeed for simplicity
        dictionary = (char**)realloc(dictionary, ++size * sizeof(char**));
        dictionary[size-1] = (char*)malloc(strlen(word)+1);
        strcpy(dictionary[size-1], word);
    }

    fclose(fp);

    // Sort the dictionary by string length
    qsort(dictionary, size, sizeof(char*), length_order);

#if defined(TEST)
    // Dump the dictionary for testing
    for (size_t x = 0; x < size; ++x)
    {
        puts(dictionary[x]);
    }
#endif

    // Clean up the dictionary
    for (size_t x = 0; x < size; ++x)
    {
        free(dictionary[x]);
    }

    free(dictionary);
}

int length_order(void const* lhs, void const* rhs)
{
    return strlen(*(char const**)rhs) - strlen(*(char const**)lhs);
}

Hi Inanna
It works now!
First, I define my dictionary data structure as the following, words are stored in an 2d array of char called word_store. each array holds words of the same length in sorted order. For example, *word_store[1] would be "amasat". counts is an array of int which keeps track of how many words has been stored in each char array in word_store.

Code:

struct dictionary{
	char *word_store[MAX_WORD_LEN];
	int counts[MAX_WORD_LEN];
} my_dic;

For LMS searching, I tried strstr on "europeaninvestmentbank" and all words in word_store[21], if no occurrence returned, I would move on to search in word_store[20] ... until a first match is found.

Basically the same at your proposal except that I try to match word of the same length or shorter than searching target.
The algorithm is not like a rocket science, but dynamic memory allocation and initialization is a real pain in the ass. Still feel like there should be a better way to do it.

Thank you!

Don't see why it's a problem to ask the same question in more than one forums, the thing I'm saying might interest people in other forums as well doesn't it?

I'm really speechless to see my post got deleted from TT forum, are forums like exclusive clubs, you can only be a member of one of those?!

Is your spirit of open source only apply within your forum?!

Originally Posted by Salem

Way to spam with the cross-posts!

C - how to find the longest meaning substring?
How to find the longest meaning substring? - Dev Shed

Though I'm betting the TT one will be gone real soon now.

Now read up on how to choose a forum

It's like ordering a pizza from 3 different places, but only acknowledging and paying the guy who shows up first with your pizza. Those other two restaurants are out the time and money on the pizza you ordered, but didn't accept or pay for, all because you're impatient. Pretty rude and selfish from the pizza company's point of view.

Read the "how to choose a forum" link Salem posted, it explains the issue in more detail.