% https://open.kattis.com/problems/welcomeeasy
% 1s
% 2.1 Easy

% Nope, regex is not the way to go...
import util.
% import regex.


main :-
  [_|S]=read_file_lines(),
  println(S),
  s(S),
  nl.
main.

% -> 7
test :-
  X = "subsequence",
  Y = "sue",
  println(count(X,Y,X.len,Y.len)).


s([]).
s([S|Ss]) :-
  T = "welcome to code jam",
  Count = count(S,T,S.len,T.len),
  println(count=Count),
  s(Ss).


% From
% https://www.techiedelight.com/count-number-times-pattern-appears-given-string-subsequence/
% """
% Function to count the number of times pattern `Y[0…n)`
% appears in a given string `X[0…m)` as a subsequence
% """
table
count(X, Y, M, N) = Ret =>
  if M == 1,N == 1 then
    % Base case 1: if only one character is left    
    Ret = cond(X[1] == Y[1],1,0)
  elseif M == 0 then
    % Base case 2: if the input string `X` reaches its end    
    Ret = 0
  elseif N == 0 then 
    % Base case 3: if pattern `Y` reaches its end, we have found subsequence
    Ret = 1
  elseif N > M then
    % Optimization: the solution is not possible if the number of characters
    % in the string is less than the number of characters in the pattern  
    Ret = 0
 else
    /*
      If the last character of both string and pattern matches,
        1. Exclude the last character from both string and pattern
        2. Exclude only the last character from the string.
    
      Otherwise, if the last character of the string and pattern do not match,
      recur by excluding only the last character in the string
    */
    Ret = cond(X[M] == Y[N], count(X, Y, M - 1, N - 1), 0) + count(X, Y, M - 1, N)
 end.

% This is not the way to go...
/*
sx([]).
sx([S|Ss]) :-
  writeln(s=S),
  regex_find_all("^.*(w.*e.*l.*c.*o.*m.*e.* .*t.*o.* .*c.*o.*d.*e.* .*j.*a.*m).*$",S,Capture),
  writeln(capture=Capture),
  writeln(len=Capture.len),
  sx(Ss).
*/