[백준 1543] 문서 검색

www.acmicpc.net/problem/1543

1543번: 문서 검색

브루트포스를 돌면 tle가 아닐까..했으나 길이가 짧아서 아닌거 같다.

 

접근 방식은 간단하다. 모든 문자열 비교 - 브루트포스이다.

처음엔 0부터 비교하는 걸로 했으나 반례가 존재했다.

ababaa
abaa

같은 로직으로 앞에서 부터 비교를 시작하면 aba까지 체크하고 a와 b가 달라서 지나가버리지만

뒤에서 부터 비교하면 abaa를 잡아낼 수 있다.  

 

 

공백이 포함된 입력값도 제공되므로 getline(cin, 문자열)을 사용해야 한다.

#include <iostream>
#include <string>

using namespace std;

string str;
string p;
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  getline(cin, str);
  getline(cin, p);

  int n = str.length();
  int m = p.length();

  int i = n - 1, j = m - 1, result = 0;
  bool flag = false;
  while (i > -1 && j > -1)
  {
    while (i > -1 && j > -1 && str[i] == p[j])
    {
      i--;
      j--;
      flag = true;
    }

    if (!flag)
    {
      i--;
    }

    if (j == -1)
    {
      result++;
    }
    j = m - 1;
    flag = false;
  }
  cout << result << "\n";
  return 0;
}