Checking if a given string S = nT

i.e to find if a given string can be represented from a substring by iterating it “n” times.

This can be done in O(N)

Let N=string length

Find all prime factors of N and for each prime factor p, consider candidate substring as  N/p length prefix of original string.

Check if the original string is repetition of candidate substring . This can be done in O(N).

Also number of prime factors of N (1<=N<=1 million) can be not more than 6. Hence we can safely say that the overall complexity is O(N).

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	vector<int> getPrimeFactors(int n){
	int limit=sqrt(n);
	vector<int> primeFactors;
	if(n%2==0){
	primeFactors.pb(2);
	n/=2;
	}
	while(n%2==0){
	n/=2;
	}
	for(int i=3;i<=limit;i+=2){
	if(n%i==0){
	primeFactors.pb(i);
	n/=i;
	}
	while(n%i==0){
	n/=i;
	}
	}
	if(n>2)
	primeFactors.pb(n);
	return primeFactors;
	}
	int main(){
	string str;
	cin>>str;
	int N=str.size();
	if(N>1){
	vector<int> p=getPrimeFactors(N);//get all prime factors of N(length of string)
	//for each factor p[i] check if prefix N/p[i] is the substring that is repeated
	string candidate;
	REP(i,p.size()){
	candidate=str.substr(0,p[i]);
	int k=0;
	int flag=1;
	FOR(j,p[i],N){
	if(candidate[k]==str[j]){
	k++;
	k%=candidate.size();
	}
	else{
	flag=0;
	break;
	}
	}
	if(flag){
	cout<<"Yes!";
	return 0;
	}
	}
	cout<<"No!";
	}
	else{
	cout<<"Not possible";
	}
	return 0;
	}

view raw checkifGivenStringSIsNT.cpp hosted with ❤ by GitHub