/****************************************************************************************
>FileName:??????exercise28.c
>Description:???
>Authot:????????zhangxu
>Date:??????????2019.04.04
>Version:???????V0.1
****************************************************************************************/

#include?

using?namespace?std;

/*****************************************************************
>?暴力法
******************************************************************/
int?Solution28::strStr（string?haystack?string?needle）?
{???
????int?m?=?haystack.size（）;
????int?n?=?needle.size（）;

????if（0?==?m?||?0?==?n）
????{
????????return?-1;
????}
????????
????for（int?i?=?0;?i?????{
????????int?j?=?0;
????????????
????????for（j?=?0;?j?????????{
????????????if（haystack[i+j]?!=?needle[j]）
????????????{
????????????????break;
????????????}
????????}
????????????
????????if（j?==?n）
????????{
????????????return?i;
????????}
????}????
????
????return?-1;???
}

/******************************************************************
>KMP方法：原理詳細講解見網址：
>https://blog.csdn.net/yangwangnndd/article/details/89042454
>https://www.cnblogs.com/en-heng/p/5091365.html
******************************************************************/
static?int?*getNext（string?needle）
{
????int?i?j;
????int?strSize?=?needle.size（）;

????int?*f?=?new?int[strSize];
????f[0]?=?-1;

????for（?j?=?1;?j?????{
????????for（i?=?f[j-1];?;?i?=?f[i]）
????????{
????????????if（needle[j]?==?needle[i+1]）
????????????{
????????????????f[j]?=?i+1;
????????????????break;
????????????}
????????????else?if（-1?==?i）
????????????{
????????????????f[j]?=?-1;
????????????????break;
????????????}
????????}
????}

????return?f;
}

int?Solution28::strStr_KMP（string?haystack?string?needle）
{
????int?i?j;
????int?*f?=?getNext（needle）;

????for（i?=?0?j?=?0;?i?????{
????????if（haystack[i]?==?needle[j]）
????????{
????????????i++;
????????????j++;
????????}
????????else?if（0?==?j）
????????{
????????????i++;
????????}
????????else
????????{
????????????j?=?f[j-1]?+?1;
????????}
????}

????delete?f;
????return?j?==?needle.size（）???i?-?needle.size（）?:?-1;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????66440??2019-04-06?09:12??leetcode\bin\test

?????文件????????493??2019-04-06?09:12??leetcode\include\leetcode.h

?????文件????????444??2019-04-06?09:12??leetcode\Makefile

?????文件??????59816??2019-04-06?09:12??leetcode\obj\exercise28.o

?????文件??????59680??2019-04-06?09:12??leetcode\obj\test.o

?????文件???????2341??2019-04-06?09:12??leetcode\src\exercise28.c

?????文件????????599??2019-04-06?09:12??leetcode\src\test.c

?????目錄??????????0??2019-04-06?09:12??leetcode\bin

?????目錄??????????0??2019-04-06?09:12??leetcode\include

?????目錄??????????0??2019-04-06?09:12??leetcode\obj

?????目錄??????????0??2019-04-06?09:12??leetcode\src

?????目錄??????????0??2019-04-06?09:12??leetcode

-----------?---------??----------?-----??----

???????????????189813????????????????????12