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

#define MAXLEN 255
typedef struct {
    // char[0]废弃不用
    char ch[MAXLEN];
    int length;
} SString;

typedef struct Node {
    // 每个结点存多个字符
    char ch[4];
    struct Node *next;
} StringNode, *String;

void AssignString(SString *s, char ch[]) {
    int length = (int)strlen(ch);
    for (int i = 0; i < length; ++i) {
        s->ch[i+1] = ch[i];
    }
    s->length = length;
}

int SubString(SString *sub, SString s, int pos, int len) {
    if (pos+len-1 > s.length) return -1;
    for (int i = pos; i < pos+len; i++) {
        sub->ch[i-pos+1] = s.ch[i];
    }
    sub->length = len;
    return 1;
}

int StringCompare(SString s, SString t) {
    for (int i = 1; i <= s.length && i<= t.length; i++) {
        if (s.ch[i] != t.ch[i]) return s.ch[i] - t.ch[i];
    }
    return s.length - t.length;
}

int Index(SString s, SString t) {
    int i = 1, n = s.length, m = t.length;
    SString sub;
    while (i <= n-m+1) {
        SubString(&sub, s, i, m);
        if (StringCompare(sub, t) !=0) i++;
        else return i;
    }
    return -1;
}

int Index1(SString s, SString t) {
    // 最坏时间复杂度: O(nm)
    int i = 1, j = 1;
    while (i<=s.length && j<=t.length) {
        if (s.ch[i]==t.ch[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > t.length) {
        return i - t.length;
    } else {
        return -1;
    }
}

void GetNext(SString t, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < t.length) {
        if (j==0||t.ch[i]==t.ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void GetNextVal(SString t, int nextVal[]) {
    int next[t.length+1];
    GetNext(t, next);
    nextVal[1] = 0;
    for (int i = 2; i < t.length; i++) {
        if (t.ch[next[i]] == t.ch[i]) {
            nextVal[i] = nextVal[next[i]];
        } else {
            nextVal[i] = next[i];
        }
    }
}

int Index_KMP(SString s, SString t) {
    int i = 1, j = 1;
    int next[t.length+1];
    GetNext(t, next);
    while (i<= s.length && j <=t.length) {
        if (j==0||s.ch[i]==t.ch[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > t.length) {
        return i - t.length;
    } else {
        return -1;
    }
}

void PrintfString(SString s) {
    for (int i = 0; i < s.length; i++) {
        printf("%c\n", s.ch[i+1]);
    }
}

int main() {
    SString s;
    AssignString(&s, "gle");
    SString sub;
    SubString(&sub, s, 1, 6);
    SString ss;
    AssignString(&ss, "googlegg");
    printf("%i\n", Index(ss, s));
    printf("%i\n", Index1(ss, s));
    printf("%i\n", Index_KMP(ss, s));
    return 0;
}