Submission #22827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22827	2017-04-30T07:45:17 Z	카시코이(#958, xdoju, ntopia, pps789)	Joyful KMP (KRIII5_JK)	C++11	0 / 7	0 ms	9972 KB

JK

#include <cstdio>
#include <cassert>
#include <vector>
#include <cstring>
#include <map>
using namespace std;

const int MOD = 1000000007;

char s[1000010];
int pi[1000010];

int par[1000010];
vector<int> neq[30];

int lst[30], lc, col[30];
map<int, int> lid;

int ans;

void dfs(int d, int cc, int k){
  if(d == lc){
    // for(int i = 0; i < lc; i++) printf("%d ", col[i]);
    // printf("\n");
    // printf("%d\n", k);
    ans += k; if(ans >= MOD) ans -= MOD;
    return ;
  }

  int vs = 0;
  for(int y : neq[d]) vs |= (1 << col[y]);

  for(int i = 0; i < cc; i++){
    if((vs & (1 << i)) == 0){
      col[d] = i; dfs(d + 1, cc, k);
    }
  }

  // new color
  col[d] = cc;
  dfs(d + 1, cc + 1, 1LL * k * (26 - cc) % MOD);
}

int getpar(int x){
  if(x == par[x]) return x;
  return (par[x] = getpar(par[x]));
}

void mer(int x, int y){
  int px = getpar(x), py = getpar(y);
  par[py] = px;
}

int main(){
  scanf("%s", s); int L = strlen(s);
  for(int i = 1; i <= L; i++) par[i] = i;

  pi[1] = 0;
  for(int k = 0, i = 2; i <= L; i++){
    while(k > 0 && s[i - 1] != s[k]){
      // printf("not equal: %d %d\n", i, k + 1);
      k = pi[k];
    }
    if(s[i - 1] == s[k]){
      // printf("equal: %d %d\n", i, k + 1);
      mer(i, k + 1);
      k++;
    }
    // else printf("not equal : %d %d\n", i, k + 1);
    pi[i] = k;
  }

  for(int i = 1; i <= L; i++){
    if(i == par[i]){
      lid[i] = lc; lst[lc++] = i;
      // printf("%d\n", i);
    }
  }

  assert(lc <= 26);

  for(int k = 0, i = 2; i <= L; i++){
    while(k > 0 && s[i - 1] != s[k]){
      int px = lid[getpar(i)], py = lid[getpar(k + 1)];
      if(px < py) neq[py].push_back(px);
      else neq[px].push_back(py);

      // printf("%d %d\n", px, py);
      k = pi[k];
    }
    if(s[i - 1] == s[k]) k++;
    else{
      int px = lid[getpar(i)], py = lid[getpar(k + 1)];
      if(px < py) neq[py].push_back(px);
      else neq[px].push_back(py);
      // printf("%d %d\n", px, py);
    }
    pi[i] = k;
  }


  dfs(0, 0, 1);

  printf("%d\n", ans);
  puts("OVER");
  return 0;
}

Compilation message

JK.cpp: In function 'int main()':
JK.cpp:55:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s); int L = strlen(s);
                 ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9968 KB	Output is correct
2	Correct	0 ms	9968 KB	Output is correct
3	Runtime error	0 ms	9972 KB	Execution killed because of forbidden syscall gettid (186)
4	Halted	0 ms	0 KB	-