https://www.acmicpc.net/problem/1431 정렬 기준에 따라 비교 함수를 만들어준다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include using namespace std; bool cmp(string &a,string &b){ int s1=a.size(),s2=b.size(); if(s1!=s2) return s1
https://www.acmicpc.net/problem/1305 길이가 N인 광고판이 있고 광고(문자열)가 광고판을 꽉 채우면서 반복되서 나타난다. 이 때 가능한 광고의 길이 중 가장 짧은 것을 찾는 문제이다. 광고가 반복해서 밀려나면서 뒤에서도 나타난다. 따라서 광고판에서 prefix와 suffix가 같을 때 길이의 최대값을 구하고 N에서 이를 빼주면 가장 짧은 광고의 길이이다. 이는 KMP에서 실패 함수의 정의이다. 123456789101112131415161718192021#include #include #include using namespace std; int main(){ int n; string s; cin>>n>>s; vector pi(n); pi[0]=0; for(int i=1,j=0;..
https://www.acmicpc.net/problem/1701 어떤 문자열의 모든 부분 문자열은 모든 suffix의 prefix들이다. 이를 이용하여 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 모든 suffix의 pi 배열을 구해서 최대값을 구해주면 된다. 1234567891011121314151617181920212223242526#include #include #include using namespace std; int main(){ string str; cin>>str; int len=str.size(),ans=0; for(int k=0;kpi[i]?ans:pi[i]; } } cout