[BOJ] 11478번 서로 다른 부분 문자열의 개수

기본적으로 sliding window같은 상황이다. 

문자열 'ababc' 위에서 나오는 부분 연속 문자열을 key로 가지는 object를 구현하면 되는데 

iteration 방식이 window 1, window2, window3을 옮기는 것이 아니라

a부터 ab, aba, abab,

b부터 ba, bab, 등 하나씩 늘어나는 방식으로 진행해야 더 효율적인 연산이 가능하다. 

1. window가 1씩 늘어나는 구현(시간초과)

let input =require('fs').readFileSync('./input.txt').toString().trim()
// console.log(input);
let chars = input.split('');
let n = chars.length;
obj={}
for(let window=1; window<=n; window++){
  for(let i=0; i <= n-window; i++ ){
    let str= chars.slice(i, i+window).join('')
    obj[str]=(obj[str]||0)
  }
}
// console.log(obj);

console.log(Object.keys(obj).length)

2. 차례차례 늘어나는 구현(정답)

slice 연산이 O(N)이라 1번의 경우 O(N^3)에 가까울 수 있다.

let input =require('fs').readFileSync('./input.txt').toString().trim()
// console.log(input);
let chars = input.split('');
let n = chars.length;
obj={}
for(let i=0; i<n; i++){
  let str=chars[i];
  for(let j=0; j < n-i ; j++ ){
    if(j!==0)str+=chars[i+j];
    // console.log(str);
    obj[str]=(obj[str]||0)+1;
  }
}
// console.log(obj);

console.log(Object.keys(obj).length)