Contents

Develop
2013.04.23 15:42

[c] kmp 활용 search

조회 수 7478 댓글 0
Atachment
첨부 '1'
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

예제 코드

#include <stdio>
#include <string>

char str[100005];
char comp[1005];
int pi[1005];

inline bool process()
{
    int i;
    int l , l2 , k;
    
    l = strlen(comp) - 1;
    // Pi 배열 생성 ; O(m)
    
    pi[1] = 0;
    k = 0;
    
    for(i=2; i<=l; i++)
    {
        while(k>0 && comp[k + 1]!=comp[i])
        {
            k = pi[k];
        }
        
        if(comp[k + 1] == comp[i]) k++;
        pi[i] = k;
    }
    // KMP 활용
    l2 = strlen(str) - 1;
    k = 0;
    
    for(i = 1; i <= l2; i++)
    {
        while(k>0 && comp[k + 1]!=str[i])
        {
            k = pi[k];
        }
        
        if(comp[k + 1] == str[i]) k++;
        if(k == l) return 1;
    }
    return 0;
}

int main()
{
    int tn , n , i;
    scanf("%d" , &tn);

    while(tn--)
    {
        scanf("%s" , str + 1);
        str[0] = ' ';
        scanf("%d" , &n);
        
        for(i = 1; i <= n; i++)
        {
            scanf("%s" , comp + 1);
            comp[0] = ' ';
            printf("%c\n" , (process()) ? 'y' : 'n');
        }
    }
    
    return 0;
}


?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
539 Develop [c++] Win32API를 이용한 ExitWindowsEx 사용한 예제코드 hooni 2013.04.23 8053
538 Develop [c#] mfc 기반의 웹서비스 서버/클라이언트 샘플과 예제 소스 secret hooni 2013.04.23 2073
537 Develop [c] 텍스트 파일(로그)을 정해진 라인 단위로 쪼개주는 코드 file hooni 2013.04.23 7092
536 Develop [c] 네트워크 트래릭 모니터링.. 졸업작품.. 2 file hooni 2013.04.23 11141
535 Develop [c#] MS IE(Internet Explorer) 툴바 버튼 예제 2003/2005 두가지 버전 secret hooni 2013.04.23 2090
534 Develop [c#] BFilter 툴바 소스 코드 ㅎㅎ file hooni 2013.04.23 7748
533 Develop [c++] mfc로 만든 현재 디렉토리 읽어오기/세팅하기 (GetCurrentDirectory/SetCurrentDirectory) file hooni 2013.04.23 8613
532 Develop 다운 받아서 테스트 해볼것.. hooni 2013.04.23 9286
531 Develop [c++] mfc 기반 멀티수납(wall)시스템 소스와 실행파일 file hooni 2013.04.23 7146
530 Develop [c++] mfc 기반 레지스트리(registry) 컨트롤 예제 코드 2 hooni 2013.04.23 15480
» Develop [c] kmp 활용 search file hooni 2013.04.23 7478
528 Develop [c] 문자열 str_shift 예제.. file hooni 2013.04.23 6899
Board Pagination Prev 1 ... 49 50 51 52 53 54 55 56 57 58 ... 98 Next
/ 98