LCSubstring

Finding Longest Common Substrings by applying Knuth-Morris-Pratt

This is a program written for the course "Fundamental Algorithms" I took. The task was to write a program to find the "Longest Common Substring" (not Longest Common Subsequence!) of two text files by applying KMP. There are far better approaches to this problem, but you know... it's university, not real life
DOWNLOAD

Prerequisites
You need GCC to compile and Posix Threads (available on all Unix/Linux systems, I don't know how to make them available on Windows, but my guess is, that it would be easier to install a new Linux system than to do that)
Compilation
Extract the files, then run

gcc -lpthread -O LCSubstring LCSubstring.c
in that folder.
Running
./LCSubstring file1 file2
Input
Two textfiles with a single string ended by "\n" (newline).
Output
l
o_1_1 o_1_2
o_2_1 o_2_2
...
o_n_1 o_n_2
With l being the length of the Longest Common Substring (or of the LCSubstrings) and the o_i_1, i between 1 and n, being the offsets in file1, the o_i_2 being the corresponding offsets in file2.
Caution: newline is always counted as a character (which is stupid but such were the requirements). So there is always a LCS of at least length 1.
Example
I split the single line, but you get the basic idea.

file1:
=+eTjFiqxbs2vax6S`COAk(6DEj36&INN4]R;4&FPR_=R?xS;<ST|p<=Ro +wu8l?k6.Tf-nGhyt2"<$U'0a]u7(tc\93^52G<q'KWJ_f?MYta'^v.{FzTy(3vXqC {V|1PEG&9/SyPI+"(6[^gB|Hbl53ypp@8?ZU;q]_?<FO&6,II4&Y"[&uKj ??%vj"082'P0J:Sqx

file2:
!odD>gK\/[3</N.\D6)4|,iQF>Bb3HD\yz<s0a7FJ&2#m5z]8ak:?s+lm2%`WHTo {iCs>Op{OWb?1)m7DI$.tJLNA;nW5w@1Ol1MhO^}L}s^@1IyOsmJd<]P2PX.8jMt'$ELFZ| 9a$[a,NCi{Q1sT4o>6c),%OzaGd1u%!kH}CHiY\:F_,jCHge!|<Pb.#P.L'!a\;2\

output:
2
82 36