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
번호 분류 제목 글쓴이 날짜 조회 수
729 Develop [ios] iCloud관련 저장 디렉토리 hooni 2013.04.23 29633
728 Develop [ios] NSData 클래스에 대해 (NSData <-> char*) hooni 2013.04.23 26567
727 Develop [ios] UILabel top alignㅎㅎ hooni 2013.04.23 22837
726 Develop [ios] UIColor 지정에서 RGB define ㅎㅎ hooni 2013.04.23 22912
725 Develop [ios] 자주 쓰는 패턴과 API hooni 2013.04.23 17688
724 Develop [ios] 테이블뷰셀/뷰에 배경 패턴 넣기.. hooni 2013.04.23 29811
723 Develop [ios] DJBros. (DJ요맨~) file hooni 2013.04.23 28100
722 Develop [ios] Debug Extensions (from 종길 차장님 ㅋㅋ) file hooni 2013.04.23 17691
721 Develop [ios] 아이폰 개발 총정리.. file hooni 2013.04.23 23861
720 Develop [ios] 구분자로 문자열 자르기 (split) hooni 2013.04.23 26267
719 Develop [iphone] view에 대한 조사 ㅡ,.ㅡ; file hooni 2013.04.23 54069
718 Develop [ios] NSMutableString 문자열 패턴 교환 hooni 2013.04.23 28989
Board Pagination Prev 1 ... 33 34 35 36 37 38 39 40 41 42 ... 98 Next
/ 98