지난 번 건 가미가제 얘기라고 해서 별 관심을 안가졌지만,

'추억의 마니'는 일단 보러갈게요.

지브리 레이아웃전 때만 해도 건재한 줄 알았는데..

7월 19일 개봉. 추억의 마니

url : http://star.mt.co.kr/stview.php?no=2014072013575479074&type=3

String Algorithms(3,5,7)

- Basic Functions : strlen, substr, strcomp

- Argorithms

문자열 검색

- 정의 : 주어진 문자열 (haystack)에서 검색문자열(needle)을 모두 찾음.

- 알고리즘 KMP : 검색 중 needle 의 접미사와 접두사가 같은 부분이 있는 경우 지금까지 일치한 부분을 기준으로 비교하지 않아도 되는 곳을 건너띄고 비교하는 방식.

- 문제 유형 : 문자열 검색 및 접두사/접미사 관련 문제.

- 문제 : 접두사/접미사(NAMING), 펜린드롬 만들기(PALINDROMIZE), 재하의 금고(JAEHASAFE)

Suffix Array

- 정의 : 접미사 배열은 문자열을 각 S[..n] 으로 쪼갠 뒤 모든 접미사를 문자열의 알파벳 순으로 정렬한 것.

- 알고리즘 : manber myers

- 문제유형 : 사전 순서 관련된 문제로 동일한 부분문자열은 항상 인접한 접미사들의 접두사로 출현한다.

- 문제 : 원형 문자열(사전 가장 앞에), 서로 다른 부분 문자열의 수, 말버릇(HABIT)

Trie(ch26)

Graph

- 위상정렬, Euiler Circuit

- 고대어 사전, 낱말 끝말잇기

Dynamic Programming(ch08, ch09)

- OCR, MORSE, RESTORE

int mystrlen(const char *str){int n=0; for(;str[n]!='\0';n++); return n;}

void mysubstr(char* dst, const char* src, int begin, int end){

    int i=begin;

    for(;i<=end;i++){dst[i-begin] = src[i];}

    dst[end+1-begin] = '\0';

}

int mystrcmp(const char* str1, const char* str2){

    int i=0;

    while(str1[i]!='\0' && str2[i]!='\0'&& str1[i] == str2[i]){i++;}

    if(str1[i]!='\0' || str2[i] !='\0'){ return str1[i] < str2[i]?-1:1;}

    if(str1[i]=='\0' && str2[i]=='\0'){return 0;}

}

#include <stdio.h>

int index[100];

size_t strlen(const char* str){

size_t n=0;

while(str[n]!='\0'){

n++;

}

return n;

}

//find H N

void naiveSearch(const char* H, const char* N){

for(int i=0;i<100;i++){

index[i] = -1;

}

size_t hN = strlen(H);

size_t nN = strlen(N);

int indexI=0;

for(unsigned int i=0;i<hN-nN;i++){

bool same = true;

for(unsigned int j=0;j<nN;j++){

if(H[i+j]!=N[j]){

same =false;

break;

}

}

if(same){

index[indexI]=i;

indexI++;

}

}

}

void main(){

naiveSearch("avadakedavra","aked");

for(int i=0;i<100 && index[i]>-1;i++){

printf("%d

",index[i]);

}

}