#include
using namespace std;
string Sub[1000];
int t=0;
int count=0;
void GenerateSubstrings(string s)
{
int l=s.length();
// int k=0;
for(int i=0;i<l;i++)
{
for(int j=1;j<=l-i;j++)
{
Sub[t]=s.substr(i, j);
// cout<<Sub[t]<<endl;
t++;
}
}
}
bool IsDivisible(string s, int n)
{
int k=0;
string ans;
int check;
// int l=s.length();
int temp=(s[k++]-‘0’);
while(temp<n)
{
temp=temp*10+(s[k++]-‘0’);
}
while((s.length()+1)>k)
{
ans+=(temp/n)+'0';
check=temp%n;
temp=(temp%n)*10+(s[k++]-'0');
}
if(check==0)
{
return true;
}
else
{
return false;
}
}
int IsMatch(string s, string str)
{
int l=str.length();
int len=s.length();
int i, j, k;
for( i=0;i<=len-l;i++)
{
k=i;
for( j=0;j<l;j++)
{
if(s[k]!=str[j])
{
break;
}
k++;
}
if(j==l)
{
break;
}
}
if(j==l)
{
return i;
}
else
{
return -1;
}
}
bool cmp(string s1, string s2)
{
return (s1.length())>(s2.length());
}
void SubstringSort(string *s)
{
for(int i=0;i<t;i++)
{
for(int j=0;j<t;j++)
{
if(cmp(Sub[j], Sub[j+1]))
{
swap(Sub[j], Sub[j+1]);
}
}
}
}
int main()
{ int n;
cin>>n;
string s;
char c[n+1];
for(int i=0;i<n;i++)
{
cin>>c[i];
s+=c[i];
}
//cout<<s<<endl;
GenerateSubstrings(s);
int IntPrimes[10];
int cnt, k=0;
for(int i=2;i<30;i++)
{
cnt=0;
for(int j=2;j<30;j++)
{
if(i%j==0)
{
cnt++;
}
}
if(cnt==1)
{
IntPrimes[k++]=i;
}
}
string StrPrimes[10];
for(int i=0;i<k;i++)
{
StrPrimes[i]=to_string(IntPrimes[i]);
}
for(int i=0;i<k;i++)
{
// cout<<StrPrimes[i]<<" ";
}
//Sort Substrings by string length
SubstringSort(Sub);
/*
for(int i=0;i<t;i++)
{
if(Sub[i].empty())
{
cout<<"empty"<<endl;
}
else
{
cout<<Sub[i]<<endl;
}
}
*/
for(int i=0;i<t;i++)
{
for(int j=0;j<k;j++)
{
if(Sub[i]==StrPrimes[j]&&IsMatch(s, Sub[i])!=-1)
{
count++;
int index=IsMatch(s, Sub[i]);
int l=StrPrimes[j].length();
// cout<<"Index "<<index<<endl;
// cout<<"Substring is:"<<Sub[i]<<endl;
for(int m=0;m<l;m++)
{
s[index]='+';
index++;
}
// cout<<Sub[i]<<endl;
// Sub[i]="";
}
}
}
// cout<<s<<endl;
for(int i=0;i<t;i++)
{
if(Sub[i]=="1"||Sub[i]=="0")
{
Sub[i]="";
}
}
/* for(int i=0;i<t;i++)
{
if(Sub[i].empty())
{
// cout<<“empty”<<endl;
}
else
{
// cout<<Sub[i]<<endl;
}
}
*/
for(int i=0;i<t;i++)
{
for(int j=0;j<k;j++)
{
if(IsDivisible(Sub[i], IntPrimes[j]))
{
Sub[i]="";
}
}
if(!Sub[i].empty()&&IsMatch(s, Sub[i])!=-1)
{
int index=IsMatch(s, Sub[i]);
for(int m=0;m<Sub[i].length();m++)
{
s[index]='+';
index++;
}
// cout<<Sub[i]<<endl;
count++;
}
}
// cout<<s<<endl;
cout<<count;
return 0;
}
My two test cases are failed!! please tell me what’s wrong in this code!!