Cod sursa(job #2428903)
Utilizator | Data | 6 iunie 2019 19:40:34 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.94 kb |
#include <bits/stdc++.h>
using namespace std;
const int N=(int)2e6+7;
int n,m;
string pat;
string s;
int ps[N];
void uga()
{
int i=1,cur=0;
while(i<m)
{
if(pat[i]==pat[cur])
{
cur++;
ps[i]=cur;
i++;
}
else
{
if(cur==0)
{
i++;
}
else
{
cur=ps[cur-1];
}
}
}
}
int sol[1000+7],cnt;
void buga()
{
int i=0,j=0;
while(i<n)
{
if(s[i]==pat[j])
{
i++;
j++;
}
if(j==m)
{
cnt++;
if(cnt<=1000)
{
sol[cnt]=i-m;
}
j=ps[j-1];
}
if(i<n && s[i]!=pat[j])
{
if(j==0)
{
i++;
}
else
{
j=ps[j-1];
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>pat>>s;
m=(int)pat.size();
n=(int)s.size();
uga(), buga();
cout<<cnt<<"\n";
if(cnt>1000)
{
cnt=1000;
}
for(int i=1;i<=cnt;i++)
{
cout<<sol[i]<<" ";
}
cout<<"\n";
return 0;
}