Pagini recente » Cod sursa (job #1119745) | Cod sursa (job #131085) | Monitorul de evaluare | Cod sursa (job #781543) | Cod sursa (job #3204448)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pat;
string txt;
string s;
int n;
long long sol;
vector <int> sol_poz;
int z[4000005];
void build()
{
s = '0' + pat + txt;
int st=1;
int dr=1;
n = s.size()-1;
for(int i = 2;i<=n;i++)
{
if(i>dr)
{
st=i;
dr=i;
while(dr<=n && s[dr] == s[dr-i+1])
dr++;
dr--;
z[i]=dr-st+1;
}
else
{
int nr_fr = i-st+1;
if(z[nr_fr]<dr-i+1)
z[i]=z[nr_fr];
else
{
st=i;
while(dr<=n && s[dr]==s[dr-i+1])
dr++;
dr--;
z[i]=dr-st+1;
}
}
}
}
int main()
{
fin>>pat>>txt;
build();
for(int i=pat.size()+1;i<=n;i++)
{
if(z[i]>=pat.size()){
sol++;
if(sol_poz.size()<1000)
sol_poz.push_back(i-pat.size()-1);
}
}
fout<<sol<<'\n';
for(auto& i : sol_poz)
fout<<i<<' ';
}