Pagini recente » Cod sursa (job #537570) | Cod sursa (job #2233935) | Cod sursa (job #1844498) | Cod sursa (job #1616596) | Cod sursa (job #2532044)
#include <bits/stdc++.h>
using namespace std;
ifstream in;
ofstream out;
string pat,s;
vector<int> ap,sol;
void pattern()
{
ap.push_back(0);
int z=1,nr=0;
while(z<pat.size())
{
if(pat[z]==pat[nr])
{
nr++;
ap.push_back(nr);
z++;
}
else
{
if(nr==0)
{
ap.push_back(0);
z++;
}
else
nr=ap[nr-1];
}
}
}
void KMP()
{
int n=s.size();
int j=0, i=0;
while (j<n)
{
if(s[j]==pat[i])
{
//int i=0;
i++;
j++;
}
if(i==pat.size())
{
sol.push_back(j-i);
i=ap[i-1];
}
else if(j<n and pat[i]!=s[j])
{
if(i!=0)
i=ap[i-1];
else
j++;
}
}
}
int main()
{
in.open("strmatch.in");
out.open("strmatch.out");
in>>pat>>s;
pattern();
KMP();
out<<sol.size()<<endl;
for(int i=0;i<sol.size();i++)
out<<sol[i]<<" ";
return 0;
}