need to find duplicate strings in file`

[e.vikaas]

Hi All,
I need to write a C code for finding the duplicate strings in a file.
the problem is all strings are concatenated in a single file.
I first need to take out the strings based on number of characters as no delimiter is present than do the comparision.
i need to get all the duplicate strings in another file.

the filesize is really huge 10 to power 8 strings.

For ex:
Input file:
abcddefgdefgghijjikl

considering the size of string is four

expected output:
defg


thanks in advance

[itCbitC]

Since when did characters become strings

[johnggold]

Are you familiar with binary tree sorts

fred
bill george
alf cal gary harold

As you pick up each character string, you "hang" them on the tree. There are plenty of libraries with the code for this.

Each node in the tree stores the character string, plus the repeat count.

If you are worried about memory, then the tree can be created as a random access file, with each record being a node, and forward/back pointers stored in each record.

As I said there is lots of library code for this.

[nonoob]

Interesting problem. There could be many duplicate strings. I suppose you want to find the longest one. I don't know an algorithm off hand. It's not a C problem until after you know an algorithm.

[Adak]

Welcome to the forum, E.Vikaas!

[johnggold]

Try this link.

Should help get you started

How to Create a Binary Tree in C | eHow.com

[laserlight]

The extraction of strings according to the given length should be rather trivial. To gain confidence, you can do that first and make sure that it is working.

One general idea to find duplicate strings is to map strings to a corresponding count of each string. Once you have constructed this map, you then iterate over it and copy those strings which counts greater than 1 to the other file. johnggold's suggestion of a (balanced) binary tree can be used to implement this map, but it is not the only applicable data structure.