Pagini recente » Cod sursa (job #2057901) | Cod sursa (job #339512) | Cod sursa (job #2055277) | Cod sursa (job #922649) | Cod sursa (job #2153109)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
string word,text;
fin>>word>>text;
vector<int>LPS(word.length());
vector<int>ans;
int i,j;
LPS[0]=0;
i=1;
j=0;
while(i<LPS.size())
{
if(word[i]==word[j])
{
j++;
LPS[i]=j;
i++;
}
else
if(j!=0)
{
j=LPS[j-1];
}
else
{
LPS[i]=0;
i++;
}
}
i=j=0;
while(i<text.length())
{
if(word[j]==text[i])
{
i++;
j++;
}
else
if(j!=0)
{
j=LPS[j-1];
}
else
{
i++;
}
if(j==word.length())
{
ans.push_back(i-j);
j=LPS[j-1];
}
}
sort(ans.begin(),ans.end());
fout<<ans.size()<<'\n';
if(ans.size()>1000)
for(int i=0;i<1000;i++)
fout<<ans[i]<<' ';
else
for(int i=0;i<ans.size();i++)
fout<<ans[i]<<' ';
fout<<'\n';
return 0;
}