方正面试的题-找出字符串最多的分解方法

本文主要是介绍方正面试的题-找出字符串最多的分解方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*同学给我一道方正面试的题，让我看看，今天把它写了下，就算练练手吧，好久没写程序了，题目如下：
有长度m(>3)的字符串M，另有n个3个字符长度的子字符串，可以是重叠的，（如123，231，），
分解字符串M,搜索与子字符串一样的字符串个数，并找出最多的分解方法。
如：Ｍ：１２３１５６７８９０。子字符串：１２３，５６７
分解Ｍ：
方法１：１２３，１５６，７８９０　　符合１个
方法２：２３１，５６７，８９０　　　符合２个
方法３：３。。。。。
所以方法２　最好，符合２个。*/

/*Author：shizhixin
Email:szhixin@gmail.com
Blog:http://blog.csdn.net/ShiZhixin
Data:Oct 29,2009
Note:程序没有错误检测措施，没有考虑时间和内存方面的优化问题*/

#include "stdafx.h"
#include <iostream>
using namespace std;

//查找n是否在数组a中,在返回true
bool IsInArray(int a[],int len,int n)
{
   for(int i=0;i<len;i++)
   {
       if(n==a[i])
       {
           return true;
       }
   }
   return false;

}

//比较两个字符串，如果相等（顺序可以不同）返回1
bool ComparStr(const char str1[],const char str2[])
{
   int i,j;
   int nFlag[3]={-1,-1,-1};
   for (i=0;i<3;i++)
       for (j=0;j<3;j++)
       {
           if (str1[i]==str2[j]&&nFlag[i]==-1&&!IsInArray(nFlag,3,j))
           {
               nFlag[i]=j;
           }
       }
       if (nFlag[0]!=-1&&nFlag[1]!=-1&&nFlag[2]!=-1)
           return true;
       else
           return false;
}

//输出字符串，从nMethodPosition开始，每个三个字符输出个逗号
void Output(const char* strSrc,int nSrcLen,int nMethodPosition)
{
   cout<<"最多的分解方法为:"<<endl;
   for(int i=0;i<nMethodPosition;i++)
       cout<<*(strSrc+i);
   if (nMethodPosition!=0)
   {
       cout<<",";
   }

   int nCommaFlag=0;
   for (i=nMethodPosition;i<nSrcLen;i++)
   {
       cout<<*(strSrc+i);
       nCommaFlag++;
       if (nCommaFlag%3==0&&i!=nSrcLen-1)
       {
           cout<<",";
       }
   }
           cout<<endl;
}

//找字符串个数，并输出分解方法
//strSrc源字符串，nSrcLen源字符串长度
//strSub需匹配的子字符串，以逗号隔开，每个串中含三个字符
//nSubNum子字符串的个数
int FindStr(const char* strSrc,int nSrcLen,const char* strSub,int nSubNum)
{
   const char* pBase=strSrc;
   int nStrNum[3]={0};
   int i,j,k;
   for (i=0;i<3;i++)
       for (j=0;j<nSrcLen/3;j++)
           for (k=0;k<nSubNum;k++)
           {
               char str1[3];
               char str2[3];
               str1[0]=*(strSrc+i+j*3);
               str2[0]=*(strSub+4*k);

               str1[1]=*(strSrc+i+j*3+1);
               str2[1]=*(strSub+4*k+1);

               str1[2]=*(strSrc+i+j*3+2);
               str2[2]=*(strSub+4*k+2);
               if (ComparStr(str1,str2))
               {
                   nStrNum[i]++;
               }
           }

           int nMax=nStrNum[0];
           int nMethodPosition=0;
           for (i=0;i<3;i++)
           {
               if (nMax<nStrNum[i])
               {
                   nMax=nStrNum[i];
                   nMethodPosition=i;
               }
           }
           Output(strSrc,nSrcLen,nMethodPosition);
           return nMax;
}

int main(int argc, char* argv[])
{
   int m;
   cout<<"输入字符串的长度:"<<endl;
   cin>>m;
   char* pM=new char[m+1];
   cout<<"输入字符串(注意为"<<m<<"个字符):"<<endl;//程序没有检测措施
   cin>>pM;
   pM[m]='/0';
   int n;
   cout<<"输入子字符串(每个串含3个字符)的个数:"<<endl;
   cin>>n;
    char* pN=new char[3*n+n-1+1];//3n字符数，n-1逗号数，1 /0
   cout<<"输入含三个字符的"<<n<<"个子字符串，之间用逗号隔开:"<<endl;
   cin>>pN; //输入时以逗号隔开
   pN[3*n+n-1]='/0';
   int nFindNum=FindStr(pM,m,pN,n);
   cout<<"符合的有"<<nFindNum<<"个"<<endl;
   cout<<endl;
    delete[] pM;
    delete[] pN;
   return 0;
}