C++アルゴリズムによる文字列マッチングの向上
アルゴリズムによる文字列マッチングの向上
問題の説明は、文字列が表示される行を見つける文字列と複数行の文字列を示します.あなたのプログラムはまた、大文字と小文字を異なる文字と見なすオプションをサポートする必要があります.オプションが開くと、同じアルファベットを表す大文字と小文字が異なる文字と見なされます.オプションをオフにすると、同じアルファベットを表す大文字と小文字は同じ文字とみなされます.
入力フォーマット入力の最初の行には、大文字と小文字の文字列Sが含まれる.2行目には、大文字と小文字が敏感なオプションを示す数値が含まれています.0の場合は大文字と小文字が敏感ではなく、1の場合は大文字と小文字が敏感です.3行目は、与えられた文字の行数を表す整数nを含む.次にn行、各行に1つの文字列が含まれ、文字列は大文字と小文字の英字で構成され、スペースやその他の文字は含まれません.
出力フォーマットは、複数行を出力し、各行に1つの文字列を含み、文字列Sを含む行を出現順に与える.
サンプル入力Hello 1 5 HelloWorldHiHiHiHelloHi GrepIsagreatTool HELLO HELLOisNOTHello
サンプル出力HelloWorldHiHiHelloHiHi HELLOisNOTHello
サンプル説明上記のサンプルでは、4番目の文字列もHelloですが、大文字と小文字が正しくありません.入力した2行目を0に変更すると、4番目の文字列が出力されます.
評価例の規模は、約1<=n<=100であり、各文字列の長さは100を超えない.
コード#コード#
1.BF解法
2.KMP解法
STL解法
問題の説明は、文字列が表示される行を見つける文字列と複数行の文字列を示します.あなたのプログラムはまた、大文字と小文字を異なる文字と見なすオプションをサポートする必要があります.オプションが開くと、同じアルファベットを表す大文字と小文字が異なる文字と見なされます.オプションをオフにすると、同じアルファベットを表す大文字と小文字は同じ文字とみなされます.
入力フォーマット入力の最初の行には、大文字と小文字の文字列Sが含まれる.2行目には、大文字と小文字が敏感なオプションを示す数値が含まれています.0の場合は大文字と小文字が敏感ではなく、1の場合は大文字と小文字が敏感です.3行目は、与えられた文字の行数を表す整数nを含む.次にn行、各行に1つの文字列が含まれ、文字列は大文字と小文字の英字で構成され、スペースやその他の文字は含まれません.
出力フォーマットは、複数行を出力し、各行に1つの文字列を含み、文字列Sを含む行を出現順に与える.
サンプル入力Hello 1 5 HelloWorldHiHiHiHelloHi GrepIsagreatTool HELLO HELLOisNOTHello
サンプル出力HelloWorldHiHiHelloHiHi HELLOisNOTHello
サンプル説明上記のサンプルでは、4番目の文字列もHelloですが、大文字と小文字が正しくありません.入力した2行目を0に変更すると、4番目の文字列が出力されます.
評価例の規模は、約1<=n<=100であり、各文字列の長さは100を超えない.
コード#コード#
1.BF解法
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int bf(string s,int switch1,string text[],int n)
{
int len1 = s.length();
// n ,
string text2[n];
for(int i=0;i<n;i++)
text2[i]=text[i];
//bf
for(int i=0;i<n;i++)
{
if(switch1==0)
transform(text[i].begin(),text[i].end(),text[i].begin(),::toupper);
int x=0,y=0;
int len2 = text[i].length();
while(x<len1&&y<len2)
{
if(x==-1||s[x]==text[i][y])
x++,y++;
else
{
y=y-x+1;
x=0;
}
}
if(x==len1)
cout<<text2[i]<<endl;
}
return 0;
}
int main()
{
int switch1,n;
string s;
cin>>s>>switch1>>n;
if(switch1==0)
transform(s.begin(),s.end(),s.begin(),::toupper);
string text[n];
for(int i=0;i<n;i++)
cin>>text[i];
bf(s,switch1,text,n);
return 0;
}
2.KMP解法
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int kmp(string s,int switch1,string text[],int n)
{
int len1 = s.length();
// kmp next
int next[len1];
int j=0,k=-1;
next[0]=-1;
while(j<len1-1)
{
if(k==-1||s[j]==s[k])
{
k++,j++;
next[j]=k;
}
else
k = next[k];
}
// n ,
string text2[n];
for(int i=0;i<n;i++)
text2[i]=text[i];
//kmp
for(int i=0;i<n;i++)
{
if(switch1==0)
transform(text[i].begin(),text[i].end(),text[i].begin(),::toupper);
int x=0,y=0;
int len2 = text[i].length();
while(x<len1&&y<len2)
{
if(x==-1||s[x]==text[i][y])
x++,y++;
else
x=next[x];
}
if(x==len1)
cout<<text2[i]<<endl;
}
return 0;
}
int main()
{
int switch1,n;
string s;
cin>>s>>switch1>>n;
if(switch1==0)
transform(s.begin(),s.end(),s.begin(),::toupper);
string text[n];
for(int i=0;i<n;i++)
cin>>text[i];
kmp(s,switch1,text,n);
return 0;
}
STL解法
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int func(string s,int switch1,string text[],int n)
{
// n ,
string text2[n];
for(int i=0;i<n;i++)
text2[i]=text[i];
//stl
for(int i=0;i<n;i++)
{
string::size_type pos=0;
if(switch1==0)
transform(text[i].begin(),text[i].end(),text[i].begin(),::toupper);
pos = text[i].find(s);
if(pos!=text[i].npos)
cout<<text2[i]<<endl;
}
return 0;
}
int main()
{
int switch1,n;
string s;
cin>>s>>switch1>>n;
if(switch1==0)
transform(s.begin(),s.end(),s.begin(),::toupper);
string text[n];
for(int i=0;i<n;i++)
cin>>text[i];
func(s,switch1,text,n);
return 0;
}