Pagini recente » Cod sursa (job #2297974) | Cod sursa (job #685731) | Cod sursa (job #2550259) | Cod sursa (job #2714848) | Cod sursa (job #2865085)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,a;
int lps[2000011],i,j,n,m;
vector <int> sol;
void lpsbuild()
{
int i=1,j=0;
while(i<n)
{
if(a[i]==a[j])
{
j++;
lps[i]=j;
i++;
}
else
if(j==0)
{
lps[i]=0;
i++;
}
else
j=lps[j-1];
}
}
void kmp()
{
int i=0,j=0;
while(i<n && sol.size()<=1000)
{
if(A[i]==a[j])
{
i++;
j++;
if(j==m)
{
sol.push_back(i-m);
j=lps[j-1];
}
}
else
if(j==0)
i++;
else
j=lps[j-1];
}
}
int main()
{
f>>a;
f>>A;
m=a.size();
n=A.size();
lpsbuild();
kmp();
g<<sol.size()<<'\n';
for(i=0;i<sol.size();i++)
g<<sol[i]<<" ";
return 0;
}