Sunday

Sunday

Sunday matches from left to right. When matching fails, inspect the text character immediately after the end of the entire current matching window. If the character is absent from the pattern, shift by the pattern length plus one. Otherwise, shift by the pattern length minus the character's rightmost index in the pattern.

The useful insight is that after a failed attempt, the character after the matching window can determine the next alignment directly.

For example, S = "bcaitsnaxzfinihao" and P = "nihao".

S[0] is b and P[0] is n, so they mismatch. The character after the window is s, which does not appear in the pattern. Shift right by the pattern length plus one: 5 + 1 = 6.

S[7] is a and P[1] is i, so they mismatch. The next character after the window is i. Its rightmost pattern index is 1, giving a shift of 5 − 1 = 4.

S[10] is f and P[0] is n, another mismatch. The character after the window is a, whose rightmost pattern index is 3. Shift by 5 − 3 = 2.

The pattern now matches completely.

Sunday

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

int sunday(const char *s, const char *p) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    int i = 0;
    int j = 0;
    int result = 0;

    while (i < s_len && j < p_len) {
        if (s[i] == p[j]) {
            i++;
            j++;
            continue;
        }

        int idx = result + p_len;
        if (idx >= s_len) {
            return -1;
        }

        int k = p_len - 1;
        while (k >= 0 && s[idx] != p[k]) {
            k--;
        }

        i = result;
        i += p_len - k;
        result = i;
        j = 0;

        if (result + p_len > s_len) {
            return -1;
        }
    }

    return j == p_len ? result : -1;
}

int main(void) {
    const char *s = "bcaitsnaxzfinihao";
    const char *p = "nihao";
    printf("%d\n", sunday(s, p));
    return 0;
}

Return the start index of the first full match, or −1 if no match exists. An empty pattern returns 0. C/C++ operate on bytes, Java on UTF-16 code units, and Python on characters; these examples use ASCII.