kmp

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

void nex(char *s, int *next)
{
    next[0] = 0;
    int now = 0, x = 1;
    while (x < strlen(s))
    {
        if (s[now] == s[x])
        {
            now += 1;
            next[x] = now;
            x += 1;
        }
        else if (now)
        {
            now = next[now - 1];
        }
        else
        {
            next[x] = 0;
            x += 1;
        }
    }
}


int main()
{
    char target[] = "dddcdabcddadcddadcddacddjaoabcdabcddadcddadcddacddababcddadabcdabcddadcddadcddacdddabcddadcddadcddacddadcdabcddadcddadcddacdddadcddacdabcddadcddadcddacdddcddadcddacddcabcddadcddadcddacddddadddadddcabcddadcddadcddacddabcddddabcddcabcddbaabcddbcabcddddcddd";
    char p[] = "dabcddadcddadcddacdd";
    int *next = NULL;
    next = (int *)malloc(sizeof(int) * strlen(p));
    nex(p, next);
    int now = 0, px = 0;
    while (now < strlen(target))
    {
        if (p[px] == target[now])
        {
            px += 1;
            now += 1;
        }
        else if (px)
            px = next[px-1];
        else
            now += 1;
        if (px == strlen(p))
        {
            printf("%d\n", now - px+1);
            px = next[px-1];
        }
    }
    return 0;
}