Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-21

PKU 3541 -- Given a string...

| 19:04 | PKU 3541 -- Given a string... - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3541 -- Given a string... - Wrong Answer -- japlj PKU 3541 -- Given a string... - Wrong Answer -- japlj のブックマークコメント

KMPやるだけ


#include<cstdio>
#include<cstring>

using namespace std;

int main()
{
  char T[5050], S[15050];
  scanf("%s%s", T, S);
  int n = strlen(S), fail[5050];
  for(int i=n; i<3*n; ++i) S[i]=S[i-n];
  fail[0] = -1;
  for(int i=1; i<n; ++i) {
    int j = fail[i-1];
    while(j >= 0 && T[i] != T[j+1]) j = fail[j];
    if(T[i] == T[j+1]) j++;
    fail[i] = j;
  }
  for(int i=0; i<n; ++i) {
    int j = -1;
    for(int k=0; k<2*n; ++k) {
      while(j >= 0 && (S[k]^S[i+k])+'0' != T[j+1]) j = fail[j];
      if((S[k]^S[i+k])+'0' == T[j+1]) ++j;
      if(j >= n-1) { puts("Yes"); return 0; }
    }
  }
  puts("No");
  return 0;
}
 |