Pagini recente » Cod sursa (job #66729) | Cod sursa (job #412816) | Cod sursa (job #2222525) | Cod sursa (job #1259181) | Cod sursa (job #2641146)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,sa[30][100005];
string s;
int LCP(int i, int j)
{
int ans=0;
int m=n-max(i,j)+1;
int p=0;
while((1<<(p+1))<=m)
{
p++;
}
for(; p>=0; p--)
{
if(sa[p][i]==sa[p][j])
{
ans+=(1<<p);
i+=(1<<p);
j+=(1<<p);
}
}
return ans;
}
int main()
{
vector<int> rez;
string a,b;
getline(f,a);
getline(f,b);
s='#'+a+'#'+b;
n=s.size()-1;
vector<pair<pair<int,int>,int>> key(200005);
for(int i=1; i<=n; i++)
{
key[i]= {{s[i],s[i]},i};
}
sort(key.begin()+1,key.begin()+n+1);
int cnt=0;
for(int i=1; i<=n; i++)
{
if(key[i].first!=key[i-1].first)
{
++cnt;
}
sa[0][key[i].second]=cnt;
}
for(int i=1; (1<<(i-1))<=n; i++)
{
for(int j=1; j<=n; j++)
{
key[j]= {{sa[i-1][j],sa[i-1][j+(1<<(i-1))]},j};
pair<pair<int,int>,int> k=key[j];
int nmmmmmm=0;
}
sort(key.begin()+1,key.begin()+n+1);
cnt=0;
for(int j=1; j<=n; j++)
{
if(key[j].first!=key[j-1].first)
{
++cnt;
}
sa[i][key[j].second]=cnt;
}
}
for(int i=a.size()+2; i<=n; i++)
{
if(LCP(1,i)>=a.size())
{
rez.push_back(i-a.size()-2);
}
}
g<<rez.size()<<'\n';
cnt=0;
for(auto it : rez)
{
++cnt;
if(cnt>1000)
{
return 0;
}
g<<it<<' ';
}
return 0;
}