user3168844 user3168844 - 4 years ago 172
Java Question

java program to check substring of another string without using substring library function

I'm trying to write a program that takes two arguments at the command line, both strings. The program checks to see whether or not the second string is a substring of the first (without using the

subst
r -- or any other library -- function). One caveat: any * in the second string can match zero or more characters in the first string, so if the input were abcd and the substring were a*c, then it would count as a substring. Also, include functionality to allow an asterisk to be taken literally if preceded by a
\
, and a
\
is taken literally except when preceding an asterisk.

any help will be appreciated.

Answer Source

KMP algorithm with implementation Link. But try to understand it. It is quite simple. Other page with similar topic. Longest substring

This is implementation from java jdk :)

  /**
     * Code shared by String and StringBuffer to do searches. The
     * source is the character array being searched, and the target
     * is the string being searched for.
     *
     * @param   source       the characters being searched.
     * @param   sourceOffset offset of the source string.
     * @param   sourceCount  count of the source string.
     * @param   target       the characters being searched for.
     * @param   targetOffset offset of the target string.
     * @param   targetCount  count of the target string.
     * @param   fromIndex    the index to begin searching from.
     */
    static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download