January 2016 – Live with passion

719

Asif NaeemJanuary 18, 2016

The solution solves the problem within time limit but there are better solutions, by sorting the array using counting sort might give a better timing. There is also a solution without using a suffix array , simply by adding the string with itself and comparing which one is the lowest sub string.

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
string str;

struct node{
	int fst,ed,idx;
}arr[20005];

int L[30][20005];

bool cmp(node a,node b)
{
	return ( (a.fst==b.fst)?(a.ed<b.ed):(a.fst<b.fst) );
}
void makesa()
{
	int len = str.size();
	int stp=1;
	for(int i=0;i<str.size();i++)
		L[0][i]=str[i]-'a';
	for(int cnt=1;cnt/2<len;cnt<<=1,stp++)
	{
		for(int i=0;i<len;i++)
		{
			arr[i].fst = L[stp-1][i];
			arr[i].ed = (i+cnt)<len?L[stp-1][i+cnt]:-1;
			arr[i].idx = i;
		}
		sort(arr,arr+len,cmp);
		for(int i=0;i<len;i++)
			L[stp][arr[i].idx]= ( (i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i );
	}
}
int main()
{
	scanf("%d",&n);
	string s;
	while(n--)
	{
		cin>>s;
		str=s;
		str.append(s);
		str.append(1u,'~');
		makesa();
		printf("%d\n",arr[0].idx+1);
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <algorithm>

using namespace std;

int n;

string str;

struct node{

int fst,ed,idx;

}arr[20005];

int L[30][20005];

bool cmp(node a,node b)

{

return ( (a.fst==b.fst)?(a.ed<b.ed):(a.fst<b.fst) );

}

void makesa()

{

int len = str.size();

int stp=1;

for(int i=0;i<str.size();i++)

L[0][i]=str[i]-'a';

for(int cnt=1;cnt/2<len;cnt<<=1,stp++)

{

for(int i=0;i<len;i++)

{

arr[i].fst = L[stp-1][i];

arr[i].ed = (i+cnt)<len?L[stp-1][i+cnt]:-1;

arr[i].idx = i;

}

sort(arr,arr+len,cmp);

for(int i=0;i<len;i++)

L[stp][arr[i].idx]= ( (i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i );

}

int main()

{

scanf("%d",&n);

string s;

while(n--)

{

cin>>s;

str=s;

str.append(s);

str.append(1u,'~');

makesa();

printf("%d\n",arr[0].idx+1);

}

return 0;

}

11512

Asif NaeemJanuary 17, 2016

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;
string str;
struct node{
	int fst;
	int ed;
	int idx;
}arr[1010];
int L[17][1010];
int RANK[1010];
int lcp[1010];
int FoundAtIndex;
int cnt;
string resStr;

bool cmp(node a,node b)
{
	return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0));
}

void suffixArray()
{
	for(int i=0;i<str.size();i++)
		L[0][i]=str[i]-'A';
	int stp=1;
	for(int cnt=1;cnt/2<str.size();cnt*=2,stp++)
	{
		for(int i=0;i<str.size();i++)
		{
			arr[i].fst=L[stp-1][i];
			arr[i].ed=(i+cnt)<str.size()?L[stp-1][i+cnt]:-1;
			arr[i].idx=i;
		}
		sort(arr,arr+str.size(),cmp);
		for(int i=0;i<str.size();i++)
		{
			L[stp][arr[i].idx]=(i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i;
		}
	}
}

int isLess(string a,string b)
{
	for(int i=0;i<a.size();i++)
	{
		if((a[i]-'0')<(b[i]-'0'))
		return 1;
		if((a[i]-'0')>(b[i]-'0'))
		return -1;
	}
	return 0;
}
int MaxLCP()
{
	for(int i=0;i<str.size();i++)
	{
		lcp[i]=0;
		RANK[arr[i].idx]=i;
	}
	string tmp;
	int k=0,j;
	int len=str.size();
	int mx=0;
	cnt=0;
	for(int i=0;i<len;i++,k?k--:0)
	{
		if(RANK[i]==str.size()-1)
		continue;
		i = arr[RANK[i]].idx;
		j = arr[RANK[i]+1].idx;
		while(i+k<len && j+k<len && str[i+k]==str[j+k])
		k+=1;
		lcp[RANK[i]]=k;
		if(mx<k)
		{
			mx=k;
			FoundAtIndex=i;
			cnt=2;
			resStr="";
			for(int l=i;l<i+k;l++)
			resStr.append(1u,str[l]);
		}
		else if(mx==k)
		{
			tmp="";
			for(int l=i;l<i+k;l++)
			tmp.append(1u,str[l]);
			int f=isLess(tmp,resStr);
			if(f==1)
			{
				resStr=tmp;
				cnt=2;
			}
			else if(f==0)
			cnt+=1;
		}

	}
	return mx;
}
int main()
{
	int n,mxLength;
	scanf("%d",&n);
	while(n--)
	{
		cin>>str;
		suffixArray();
		mxLength = MaxLCP();
		if(mxLength==0)
		{
			printf("No repetitions found!\n");
		}
		else
		{
			cout<<resStr<<" "<<cnt<<"\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

string str;

struct node{

int fst;

int ed;

int idx;

}arr[1010];

int L[17][1010];

int RANK[1010];

int lcp[1010];

int FoundAtIndex;

int cnt;

string resStr;

bool cmp(node a,node b)

{

return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0));

}

void suffixArray()

{

for(int i=0;i<str.size();i++)

L[0][i]=str[i]-'A';

int stp=1;

for(int cnt=1;cnt/2<str.size();cnt*=2,stp++)

{

for(int i=0;i<str.size();i++)

{

arr[i].fst=L[stp-1][i];

arr[i].ed=(i+cnt)<str.size()?L[stp-1][i+cnt]:-1;

arr[i].idx=i;

}

sort(arr,arr+str.size(),cmp);

for(int i=0;i<str.size();i++)

{

L[stp][arr[i].idx]=(i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i;

}

int isLess(string a,string b)

{

for(int i=0;i<a.size();i++)

{

if((a[i]-'0')<(b[i]-'0'))

return 1;

if((a[i]-'0')>(b[i]-'0'))

return -1;

}

return 0;

}

int MaxLCP()

{

for(int i=0;i<str.size();i++)

{

lcp[i]=0;

RANK[arr[i].idx]=i;

}

string tmp;

int k=0,j;

int len=str.size();

int mx=0;

cnt=0;

for(int i=0;i<len;i++,k?k--:0)

{

if(RANK[i]==str.size()-1)

continue;

i = arr[RANK[i]].idx;

j = arr[RANK[i]+1].idx;

while(i+k<len && j+k<len && str[i+k]==str[j+k])

k+=1;

lcp[RANK[i]]=k;

if(mx<k)

{

mx=k;

FoundAtIndex=i;

cnt=2;

resStr="";

for(int l=i;l<i+k;l++)

resStr.append(1u,str[l]);

}

else if(mx==k)

{

tmp="";

for(int l=i;l<i+k;l++)

tmp.append(1u,str[l]);

int f=isLess(tmp,resStr);

if(f==1)

{

resStr=tmp;

cnt=2;

}

else if(f==0)

cnt+=1;

}

return mx;

}

int main()

{

int n,mxLength;

scanf("%d",&n);

while(n--)

{

cin>>str;

suffixArray();

mxLength = MaxLCP();

if(mxLength==0)

{

printf("No repetitions found!\n");

}

else

{

cout<<resStr<<" "<<cnt<<"\n";

}

return 0;

}

11022

Asif NaeemJanuary 2, 2016

This is a dp problem where kmp algorithm(specially prefix function) is used to solve the problem. If a string is multiple of a repeated string then the difference between the string length and last index of the prefix table indicates the minimal length of the repeated string. A brief and nice discussion is available here .

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define INF 100000000
using namespace std;

int dp[85][85];
int lps[85];
string s;
int prefix_function(string str)
{
	memset(lps,0,sizeof(lps));
	int len = 0;
	int i=1;
	lps[0]=0;
	int length = str.size();
	while(i<length)
	{
		if(str[i]==str[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				len = 0;
				i+=1;
			}
		}
	}
	int minimal_lengthOf_repeated_str = str.size()-lps[str.size()-1];
	int times = str.size()/minimal_lengthOf_repeated_str;
	if(str.size()==times*minimal_lengthOf_repeated_str)
	return minimal_lengthOf_repeated_str;
	else
	return str.size();
}

int DP(int left,int right)
{
	if(left==right)
	return 1;
	if(dp[left][right]!=-1)
		return dp[left][right];
	string str1 = s.substr(left,right-left+1);
	int val = prefix_function(str1);
	int ans1,ans2;
	if(val==right-left+1)
	{
		int mn = INF;
		for(int i=left;i<right;i++)
		{
			ans1 = DP(left,i);
			ans2 = DP(i+1,right);
			mn = (mn<(ans1+ans2)?mn:(ans1+ans2));
		}
		dp[left][right]=mn;
	}
	else
	{
		dp[left][right] = DP(left,left+val-1);
	}
	return dp[left][right];
}

int main()
{
	while(cin>>s)
	{
		if(s=="*")
		break;
		memset(dp,-1,sizeof(dp));
		printf("%d\n",DP(0,s.size()-1));
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#define INF 100000000

using namespace std;

int dp[85][85];

int lps[85];

string s;

int prefix_function(string str)

{

memset(lps,0,sizeof(lps));

int len = 0;

int i=1;

lps[0]=0;

int length = str.size();

while(i<length)

{

if(str[i]==str[len])

{

len+=1;

lps[i]=len;

i+=1;

}

else

{

if(len!=0)

{

len = lps[len-1];

}

else

{

len = 0;

i+=1;

}

int minimal_lengthOf_repeated_str = str.size()-lps[str.size()-1];

int times = str.size()/minimal_lengthOf_repeated_str;

if(str.size()==times*minimal_lengthOf_repeated_str)

return minimal_lengthOf_repeated_str;

else

return str.size();

}

int DP(int left,int right)

{

if(left==right)

return 1;

if(dp[left][right]!=-1)

return dp[left][right];

string str1 = s.substr(left,right-left+1);

int val = prefix_function(str1);

int ans1,ans2;

if(val==right-left+1)

{

int mn = INF;

for(int i=left;i<right;i++)

{

ans1 = DP(left,i);

ans2 = DP(i+1,right);

mn = (mn<(ans1+ans2)?mn:(ans1+ans2));

}

dp[left][right]=mn;

}

else

{

dp[left][right] = DP(left,left+val-1);

}

return dp[left][right];

}

int main()

{

while(cin>>s)

{

if(s=="*")

break;

memset(dp,-1,sizeof(dp));

printf("%d\n",DP(0,s.size()-1));

}

return 0;

}

Continue Reading “11022” →

Month: January 2016

719

11512

11022

Archives

Categories