View Code of Problem 3832

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

void mark(char str[],int s[]);

char str1[100001],str2[100001];

int main() {
    int str[100001];
    int len1,len2;
    int i,j,j1;
    //读入
    while(gets(str1)!=NULL) {
        gets(str2);
        len1 = strlen(str1);
        len2 = strlen(str2);
    //赋值
        mark(str2,str);
    //遍历
        j=0;
        for(i=0;i<len1;i++) {
            for(;j<len2;j++) {
                if(str1[i]==str2[j]) {
                    i++;
                }
                else {
                    break;
                }
            }
            if(j>=len2) {
                break;
            }
            else {
                for(j1=j;j1>=0;j1--) {
                    if(str[j1]!=-1) {
                        i = i - (j-j1);
                        j = str[j1];
                        break;
                    }
                }
                if(j1<0) {
                    j = 0;
                }
            }
        }
        if(j>=len2) {
            printf("%d\n",i-j+1);
        }
        else {
            printf("-1\n");
        }
    }
}

void mark(char str[],int s[]) {
    int len = strlen(str);
    int j;
    s[0]=-1;
    for(j=1;j<len;j++) {
        if(s[j-1]!=-1&&str[j]==str[s[j-1]+1]) {
            s[j] = s[j-1]+1;
        }
        else {
            if(str[j]==str[0]) {
                s[j] = 0;
            }
            else {
                s[j] = -1;
            }
        }
    }
}