Introduction

Given two strings s1 and s2, find if s1 is a substring of s2.

Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation:
String "for" is present as a substring
of s2.

Input: s1 = "practice", s2 = "geeksforgeeks"
Output:
Explanation:
There is no occurrence of "practice" in
"geeksforgeeks"

Examples

Approach

We can use the KMP Algorithm. The idea behind KMP is “recovering” from mismatches by using partial match information to skip over positions where the pattern can’t possibly be found and avoid redoing comparisons where we already know that a prefix of the pattern matches the main string.

In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory. Morris and Vaughan Pratt published a technical report in 1970. The three also published the algorithm jointly in 1977.

KMP is done using the LPS (longest possible suffix which is also a prefix), also thought as a Partial Match Table.

Refer to the the previous article for Find the continuous pattern in a given string.

Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.

Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”.

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

aba - longest prefix and longest suffix that are equal a length is 1
abba - longest prefix and longest suffix that are equal ab length is 2
ababa - longest prefix and longest suffix that are equal aba length is 3

Example

W = "ABCDABD" and S = "ABC ABCDAB ABCDABCDABDE"

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:    ABCDABD
i:    0123456

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:           ABCDABD
i:           0123456

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

Understanding on KMP and LPS

Code

We compute the Partial Match Table (LPS) and we sue it to perform the substring search. For any mismatch, we try to move the pattern based on the LPS, or increment the main string index otherwise.

Program

using System;

public class Test
{
    public static void Main()
    {
        var pattern = Console.ReadLine();
        var main = Console.ReadLine();
        SubstringSearch(pattern, main);
    }
    private static void SubstringSearch(string pattern, string main)
    {
        var lps = CompulteLps(pattern);
        var i = 0;
        var n = pattern.Length;

        var j = 0;
        var m = main.Length;

        while (j < m)
        {
            if (pattern[i] == main[j])
            {
                i++;
                j++;
            }
            else
            {
                if (i != 0)
                {
                    i = lps[i - 1];
                }
                else
                {
                    j++;
                }
            }

            if (i != n)
            {
                continue;
            }
            // write and set i to lps[i - 1] to find the next one
            Console.WriteLine(j - i);
            i = lps[i - 1];
        }
    }

    // longest prefix which is also a suffix
    private static int[] CompulteLps(string pattern)
    {
        var n = pattern.Length;
        var lps = new int[n];
        var index = 0;
        for (var i = 1; i < n;)
        {
            if (pattern[i] == pattern[index])
            {
                lps[i] = index + 1;
                index++;
                i++;
            }
            else // pattern[i] != pattern[index]
            if (index != 0)
            {
                // use the computation to adjust to previous match
                // without incremeneting i
                index = lps[index - 1];
            }
            else // index is zero
            {
                lps[i] = 0;
                i++;
            }
        }
        return lps;
    }
}

KMP Algorithm

Check if a string is a substring of another

Varun Chopra