Pagini recente » Cod sursa (job #157708) | Cod sursa (job #3283051) | Cod sursa (job #2970980) | Cod sursa (job #1960517) | Cod sursa (job #2641432)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
string A, B, sir;
int Suffix[30][200005];
int lg[200005];
pair <pair <int, int>, int> K[200005];
void Suffix_Array () {
lg[1] = 0;
for (int i = 2; i <= sir.size(); ++ i ) {
lg[ i ] = lg[ i / 2 ] + 1;
}
for (int j = 0; j < sir.size(); ++ j ) {
K[ j ] = {{sir[j], 0}, j};
}
sort(K, K+sir.size());
int cnt = 1;
Suffix[0][K[0].second] = 1;
for (int j = 1; j < sir.size(); ++ j ) {
if (K[j].first != K[j-1].first) ++ cnt;
Suffix[0][K[j].second] = cnt;
}
for (int i = 1; (1<<(i-1)) <= sir.size(); ++ i ) {
for (int j = 0; j < sir.size(); ++ j ) {
K[ j ] = {{Suffix[i-1][j], Suffix[i-1][j+(1<<(i-1))]}, j};
}
sort(K, K+sir.size());
int cnt = 1;
Suffix[i][K[0].second] = 1;
for (int j = 1; j < sir.size(); ++ j ) {
if (K[j].first != K[j-1].first) ++ cnt;
Suffix[i][K[j].second] = cnt;
}
}
}
int LCP (int i, int j) {
int ans = 0, M = (int)sir.size() - max(i, j);
for (int p = lg[M]; p >= 0; -- p ) {
if (Suffix[p][i] == Suffix[p][j]) {
ans += (1<<p);
i += (1<<p);
j += (1<<p);
}
}
return ans;
}
int main()
{
f >> A >> B;
sir = B + A;
Suffix_Array();
vector <int> sol;
for (int i = 0; i <= (int)B.size() - (int)A.size(); ++ i ) {
int val = LCP(i, B.size());
if (val >= A.size()) {
sol.push_back(i);
}
}
g << sol.size() << '\n';
for (int i = 0; i < min(1000, (int)sol.size()); ++ i ) {
g << sol[ i ] << " ";
}
return 0;
}