Поиск подстроки в строке

{a₀, a₁, … a_n-1 ; b₀, b₁, … b_m-1 }

Поиск подстроки B в строке A

{b₀=a_i, b₁=a_i+1,…b_n=a_i+m-1 или i не существует}

{a₀, a₁, … a_n-1 ; b₀, b₁, … b_m-1 }

Для i от 0 до n-1

Если (b₀=a_i, b₁=a_i+1,…b_n=a_i+m-1 ) – результат – i, закончить цикл

Если нет результата – подстрока не найдена.

{b₀=a_i, b₁=a_i+1,…b_n=a_i+m-1 или i не существует}

Пример программы:

int search(char* needle, int nlen, char* haystack, int hlen)

/*

Поиск подстроки needle длиной nlen в строке haystack длиной hlen.

Алгоритм грубой силы.

*/

{

int i, j=0;

for (i=0; (i<hlen)&&(j<nlen); i++)

for(j=0; (j<nlen)&&(needle[j]==haystack[i+j]);j++);

if (j==nlen) return i; else return 0;

}

main()

{

char haystack[] = "acabcabacc";

char needle[3][4] = {"cc",

"aca",

"bca"};

int len[]={2, 3, 3};

int ans[]={9, 1, 4};

int i, ntest=3, n;

for(i=0;i<ntest;i++)

{

printf("tets %i\n", i);

n = search(needle[i], len[i], haystack, sizeof(haystack)-1);

printf("Substring \"%s\" in string \"%s\" in %i position\n", needle[i], haystack, n);

if (n==ans[i]) printf("test passed\n\n");

else printf("test failed\n\n");

} }