XDOJ.T81_문자열 찾기

다른 글 에서 XDOJ. T204단어 통계 (초 강력 알고리즘) 에서 가난 한 자동 동기 가 있 는 기본 적 인 용법 을 소개 한 후 다시 유연 하 게 활용 해 보 자.예 를 들 면 이 문제.
표제
문자열 찾기
유별
문자열 처리
시간 제한
2S
메모리 제한
256Kb
문제 설명
문자열 과 여러 줄 의 문 자 를 보 여 줍 니 다. 출력 은 이 텍스트 에 지정 한 문자열 의 줄 이 나 타 났 습 니 다.프로그램 은 대소 문자 민감 한 옵션 도 지원 해 야 합 니 다. 옵션 이 열 렸 을 때 같은 자모의 대문자 와 소문 자 를 다른 문자 로 간주 합 니 다.옵션 이 닫 혔 을 때 같은 자모의 대문자 와 소문 자 를 같은 문자 로 표시 합 니 다.
입력 설명
입력 데이터 첫 줄 에는 대소 문자 영문 자모 로 구 성 된 문자열 s 가 포함 되 어 있 으 며 길이 가 100 을 넘 지 않 습 니 다.두 번 째 줄 에는 대소 문자 민감 옵션 을 나타 내 는 숫자 가 포함 되 어 있 습 니 다.숫자 가 0 일 때 는 대소 문자 가 민감 하지 않다 는 뜻 이 고, 숫자 가 1 일 때 는 대소 문자 가 민감 하 다 는 뜻 이다.세 번 째 줄 은 정수 n 을 포함 하여 제 시 된 텍스트 줄 수 를 표시 합 니 다.(n 의 수치 범 위 를 지정 하지 않 았 습 니 다. n < = 100, 만점 을 받 을 수 있 습 니 다) 다음 n 줄 은 하나의 문자열 을 포함 하고 문자열 은 대소 문자 영문 자모 로 구성 되 며 빈 칸 과 다른 문 자 를 포함 하지 않 습 니 다.각 문자열 의 길 이 는 100 을 초과 하지 않 습 니 다.
출력 설명
여러 줄 을 출력 합 니 다. 줄 마다 문자열 이 포함 되 어 있 습 니 다. 문자열 s 가 포 함 된 줄 을 순서대로 보 여 줍 니 다.
입력 샘플
Hello 1 5 HelloWorld HiHiHelloHiHi GrepIsAGreatTool HELLO HELLOisNOTHello
출력 샘플
HelloWorld HiHiHelloHiHi HELLOisNOTHello
이 문제 에 대해 말하자면, 단지 두 가지 상태 일 뿐이다

찾 으 려 는 단어의 대응 자모 (LETTER)

가 아 닙 니 다.

현재 자 모 는 바로 찾 아야 할 단어의 대응 자모 이 고 n 번 째 자모의 상 태 는 n 으로 표시 합 니 다 (WORD,...)

#include 
#include 

#define WORD 1
#define LETTER -1

int main()
{
    char word[101];
    gets(word);
    int sensi; //sensitivity(  )，            
    int n;
    scanf("%d%d",&sensi,&n);
    getchar();
    if(!sensi)strupr(word); // sensi  0，       ，     word           
    char str[101][101],str1[101];   /*    str1            str     
                                                  */
    int i=0,j;
    for(;i<n;++i)
    {
        gets(str[i]);
    }
    int state=LETTER;
    int len=strlen(word);
    for(i=0;i<n;++i)
    {
        strcpy(str1,str[i]);
        if(!sensi)
        {
            strupr(str1);   //        ，              str   
        }
        int done=0; /*            ，             ，               ，
                    done                 */
        for(j=0;str1[j];++j)
        {
//            printf("J:%d STATE:%d
",j,state);
            switch(state)
            {
            case(LETTER):
                if(str1[j]==word[0])state=WORD;
                break;
            default:
                if(state<len)
                {
                    if(str1[j]==word[state])++state;
                    else
                    {
                        j-=state;   /*            
                                            ，     */
                        state=LETTER;   //        
                    }
                }
                else if(state==len)
                {
                    printf("%s
",str[i]);  //        ，      str1        ，      str[i]
                    done=1; 
                    state=LETTER;
                }
            }
            if(done)break;  //               ，  done  1，break,          
        }
        if(state==len&&!done)   //               ，  done  1，      
        {
            printf("%s
",str[i]);
            state=LETTER;
        }
    }
    return 0;
}

상태 가 두 가지 밖 에 없 는 것 을 제외 하고 본 문 제 는 아직도 많은 특수 한 점 이 있다.

프로그램 은 대소 문자 민감 한 옵션 도 지원 해 야 합 니 다. 옵션 이 열 렸 을 때 같은 자모의 대문자 와 소문 자 를 다른 문자 로 간주 합 니 다.옵션 이 닫 혔 을 때 같은 자모의 대문자 와 소문 자 를 같은 문자 로 표시 합 니 다.출력 결과 의 정확성 을 확보 하기 위해 문자 배열 str 1

을 따로 정의 하 였 습 니 다.

입력 해 야 할 문자열 이 여러 줄 이 므 로 2 차원 문자 배열 str

을 정의 합 니 다.

출력 해 야 할 것 은 단어 가 나타 나 는 횟수 가 아니 라 찾 은 단 어 를 포함 하 는 문자열 입 니 다. 변 수 는 done 으로 특정한 상황 에서 중복 출력 을 피 할 수 있 습 니 다

j - = state 에 대해 서 는 어떤 특수 한 상황 에 대해 반드시 이렇게 해 야 한다.예 를 들 어 이러한 입력 사례:

HeHeh 1 1 HeHeHeheH
'j - = state;' 라 는 문 구 를 추가 하지 않 으 면 프로그램 이 'HeHeHeheH' 의 세 번 째 'H' 를 검 사 했 을 때 state 가 LETTER 로 바 뀌 고 다음 순환 전에 j 가 1 을 추가 한 다음 프로그램 이 세 번 째 'e' 를 검사 하기 시작 하면 출력 이 없 음 을 발견 할 수 있 습 니 다.물론 이 문 제 는 더 간단 한 알고리즘 이나 사고 가 있 을 수 있다.만약 사내 들 이 있다 면, 나 는 반드시 귀 담아 들 어야 한다.