بهینه ترین حالت سرچ زیر رشته چه طور هست؟

[sajad dp]

سلام
ی سوال داشتم حل می کردم نیاز هست ک داخلش زیر رشته چک بشه
کارش هم این هست ک چندتا عدد بگیره و باهم چکشون کنه مثلا اگر اعداد باشه:
123
1234
564684
چاپ کنه No ( یعنی اگر یکی از اعداد وارد شده ب طور کامل اوله یکی از اعداد دیگه باشه چاپ کنه No )
و اگه باشه:
12340
12345
1234968
654123401356
چاپ کنه Yes.

این طوری نوشتم و کار میکنه:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include "time.h"

using namespace std;
int main()
{
int t,n,*p;vector<string> v;
cin>>t;
clock_t start = clock() ;
for ( int i=0;i<t;i++)
{
cin>>n;
v.resize(n);
for(int j=0;j<n;j++)
{
cin>>v[j];
}
sort(v.begin(),v.end());
for ( int j=0;j<v.size();j++)
{
for ( int k=j+1;k<v.size();k++)
{
n= v[k].find(v[j]);
if ( n == 0)
break;
}
if ( n == 0)
break;
}
if ( n == 0)
cout<<"NO\n";
else
cout<<"YES\n";
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
}


return 0;
}

مشکلم این هست که اصلا بهینه نیست و مثلا برای 10000 تا داده حدودا 26 ثانیه طول می کشه تا محاسبه کنه!
ب نظرتون چ طوری می تونم کد رو بهینه تر کنم؟

[UfnCod3r]

من از حرف های شما چیزی نفهمیدم. می خوای ی رشته رو تو ی رشته دیگه جستجو کنی ببینی هست یا نه ؟ همون تابع strstr ?
:عصبانی++:

[omid_kma]

3 تا for رو تو در تو نوشتی طبیعیه که برای تعداد بالا تا این قدر طول بکشه O(n^3 ...

[rahnema1]

سلام
شما می تونید یک تابع در ابتدا به این صورت تعریف کنید:

bool lower( const strin& x,const string& y)
{
return stoul(x)< stoul(y);
}

و بعد هم sort را به این صورت بنویسید

sort(v.begin(),v.end(),lower);

[hadi0x7c7]

شما میتونید از الگوریتم KMP و یا از Aho–Corasick string matching algorithm استفاده کنید، البته بگم که کار با اینا یکم سخته

[omid_kma]

std::sort از quick sort استفاده می کنه که performance بهتری نسبت به heap sort داره

[rahnema1]

با عرض معذرت اون پست که گذاشتم که از sort استفاده می کنه جواب اشتباه میده. ولی این یکی دیگه رد خور نداره هنگام وارد شدن داده ها چک می کنه که یکی از اونها در ابتدای اون یکی هست یا نه یعنی دیگه لازم نیست ایتدا داده ها به طور کامل وارد بشن بعد عملیات روی اونها انجام بشه . به محض وارد شدن چک میشن

#include <set>
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
clock_t start;
template< class T >
struct less1
{
bool operator()(const T &x, const T &y) const
{
if(x.length()<y.length())
{
if(!y.find(x))
{
printf("NO\n");
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
exit(0);
}
}
else if(!x.find(y))
{
printf("NO\n");
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
exit(0);
}
return x < y;
}
};

int main( )
{
srand(time(NULL));
int n=1000000;
set <string, less1<string> > s1;
start = clock() ;
for(int j=0; j<n; j++)
{
s1.insert(to_string(rand()%(n*100)));
}
cout<<"YES\n";
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
return 0;
}

[omid_kma]

با عرض معذرت اون پست که گذاشتم که از sort استفاده می کنه جواب اشتباه میده. ولی این یکی دیگه رد خور نداره هنگام وارد شدن داده ها چک می کنه که یکی از اونها در ابتدای اون یکی هست یا نه یعنی دیگه لازم نیست ایتدا داده ها به طور کامل وارد بشن بعد عملیات روی اونها انجام بشه . به محض وارد شدن چک میشن
برای تست بدترین حالت(وقتی که yes چاپ بشه ) می تونین از این کد استفاده کنین :
#include <set>
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
clock_t start;
template< class T >
struct less1
{
bool operator()(const T &x, const T &y) const
{
if(x.length()<y.length())
{
if(!y.find(x))
{
printf("NO\n");
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
exit(0);
}
}
else if(!x.find(y))
{
printf("NO\n");
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
exit(0);
}
return x < y;
}
};

void calcPermutation(string & num,unsigned int count,vector<string>&container)
{
if(count == 0)
return;

count--;

container[count]= num;



if(num[0]=='9')
{
for(unsigned int i=1;i<num.size();i++)
{
if(num[i] != '9')
{
num[i]++;
for(unsigned int j=0;j<i;j++)
{
num[j]='0';
}
break;
}
}

}
num[0] ++;
calcPermutation(num,count,container);

}

int main( )
{
srand(time(NULL));
unsigned int n=9000000;

std::vector<string> container(n);

string p="0000000000";
calcPermutation(p,n,container);

set <string, less1<string> > s1;
start = clock() ;
for(int j=0; j<n; j++)
{
s1.insert(container[j]);
}
cout<<"YES\n";
printf ( "Time elapsed: %f\n" , ((double)clock() - start) / CLOCKS_PER_SEC );
return 0;
}

[rahnema1]

ببینید فکر کنم گفته شما درست نباشه
بدترین حالت quicksort برابر n^2 هست وبدترین حالت برای وقتی که yes باشه برابر sum(k)|k=1:n یا2 / (n^2+n) هست بنابراین هزینه الگوریتم موجود در پست اول که دوستمون گذاشتن در بدترین
حالت برابر با

1.5*n^2+0.5*n

خواهد بود اما این مورد که گذاشتم از set استفاده می کنه که در واقع یک درخت قرمز و سیاه است که برای insert هزینه logn داره که n تا insert داریم پس در بدترین حالت (!log(n خواهد بود حتی اگه بگیم همراه با insert عملیات search هم انجام میشه که هزینه اون logn هست هزینه کلی برابر با (!2log(n خواهد بود

[sajad dp]

من از حرف های شما چیزی نفهمیدم. می خوای ی رشته رو تو ی رشته دیگه جستجو کنی ببینی هست یا نه ؟ همون تابع strstr ?

آره سوالش اینه : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2347


شما میتونید از الگوریتم KMP و یا از Aho–Corasick string matching algorithm استفاده کنید، البته بگم که کار با اینا یکم سخته

ممنونم، میشه یک منبع در این مورد معرفی کنید؟

---------------
دوستان عزیز omid_kma و rahnema1 بابت توضیحاتتون ممنونم، روش کلی دستم اومد (:

[hadi0x7c7]

توی سایت topcoder و یا همون خود ویکی پدیا:قهقهه: