各単語が回文であるように単語を分割する方法の数を見つけるためのC++プログラム

ここでは、各単語が回文になるように単語を分割するいくつかの方法を見つけるためのC++プログラムについて説明します。

アルゴリズム

Begin
   Take the word as input.
   Function partitionadd(vector<vector<string> > &u, string &s, vector<string> &tmp, int index):
   if (index == 0)
      tmp.clear()
   for i = index to length-1
      st = st + s[i]
      if (checkPalin(st))
         tmp.push_back(st)
         if (i+1 < length)
            partitionadd(u, s, tmp, i+1)
         else
            u.push_back(tmp)
               tmp = curr
   return
End
Begin
   Function partition(string st, vector<vector<string> >&u):
      vector<string> tmp
      addStrings(u, st, tmp, 0)
      printSol(u) //to print the solution
   return
End

例

#include <bits/stdc++.h>
using namespace std;

bool checkPalin(string s) { //check if string is palindrome or not.
   int length = s.length();
   length--;
   for (int i=0; i<length; i++) {
      if (s[i] != s[length])
      return false;
      length--;
   }
   return true;
}
void printSol(vector<vector<string> > part) { //print the solution
   for (int i = 0; i < part.size(); ++i) {
      for(int j = 0; j < part[i].size(); ++j)
      cout << part[i][j] << " ";
      cout << endl;
   }
   return;
}
void partitionadd(vector<vector<string> > &u, string &s, vector<string> &tmp, int index) {
   int length = s.length(); //store length of the string
   string st;
   vector<string> curr = tmp;
   // goes through all indexes and recursively add remaining partitions if current string is palindrome.
   if (index == 0)
   tmp.clear();
   for (int i = index; i < length; ++i) {
      st = st + s[i];
      if (checkPalin(st)) {
         tmp.push_back(st);
         if (i+1 < length)
            partitionadd(u,s,tmp,i+1);
         else
            u.push_back(tmp);
         tmp = curr;
      }
   }
   return;
}
void partition(string st, vector<vector<string> >&u) //generate all palindromic partitions of 'str' and stores the result in 'm'. {
   vector<string> tmp;
   addStrings(u, st, tmp, 0);
   printSol(u);
   return;
}
int main() {
   string s = "tutorials";
   vector<vector<string> > part;
   cout<<"the number of partitions:"<<endl;
   partition(s, part);
   return 0;
}

出力

the number of partitions:
t u t o r i a l s
tut o r i a l s