Contents

Develop
2013.04.23 15:42

[c] kmp 활용 search

조회 수 7405 댓글 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
번호 분류 제목 글쓴이 날짜 조회 수
537 Develop [c] 텍스트 파일(로그)을 정해진 라인 단위로 쪼개주는 코드 file hooni 2013.04.23 7036
536 Develop [c] 네트워크 트래릭 모니터링.. 졸업작품.. 2 file hooni 2013.04.23 11037
535 Develop [c#] MS IE(Internet Explorer) 툴바 버튼 예제 2003/2005 두가지 버전 secret hooni 2013.04.23 2090
534 Develop [c#] BFilter 툴바 소스 코드 ㅎㅎ file hooni 2013.04.23 7596
533 Develop [c++] mfc로 만든 현재 디렉토리 읽어오기/세팅하기 (GetCurrentDirectory/SetCurrentDirectory) file hooni 2013.04.23 8432
532 Develop 다운 받아서 테스트 해볼것.. hooni 2013.04.23 9129
531 Develop [c++] mfc 기반 멀티수납(wall)시스템 소스와 실행파일 file hooni 2013.04.23 7042
530 Develop [c++] mfc 기반 레지스트리(registry) 컨트롤 예제 코드 2 hooni 2013.04.23 14899
» Develop [c] kmp 활용 search file hooni 2013.04.23 7405
528 Develop [c] 문자열 str_shift 예제.. file hooni 2013.04.23 6829
527 Develop [c++] winsock을 이용한 서버,클라이언트와 ssl서버,클라이언트 file hooni 2013.04.23 7600
526 Develop [c++] mfc이용한 트레이아이콘(TrayIcon) 클래스 예제 프로젝트 file hooni 2013.04.23 9239
Board Pagination Prev 1 ... 49 50 51 52 53 54 55 56 57 58 ... 98 Next
/ 98