Pagini recente » Cod sursa (job #2547582) | Cod sursa (job #1418969) | Cod sursa (job #1310223) | Cod sursa (job #2961152) | Cod sursa (job #3125464)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[2000005];
int main()
{
string a, b;
fin>>a>>b;
int prevLPS=0;
for(int i=1; i<a.size();)
{
if(a[i] == a[prevLPS])
{
lps[i]=++prevLPS;
i++;
}
else if(prevLPS > 0)
{
prevLPS=lps[prevLPS-1];
}
else
{
lps[i]=0;
i++;
}
}
int i=0; // b
int j=0; // a
vector<int> ans;
while(i < b.size())
{
if(b[i] == a[j])
{
i++;
j++;
}
else
{
if(j == 0)
{
i++;
}
else
{
j=lps[j-1];
}
}
if(j == a.size())
{
ans.push_back(i-a.size());
}
}
fout<<ans.size()<<'\n';
for(int i=0; i<min(1000, (int)ans.size()); i++)
fout<<ans[i]<<" ";
return 0;
}