Pagini recente » Cod sursa (job #1180398) | Cod sursa (job #2084099) | Cod sursa (job #1571518) | Cod sursa (job #2158229) | Cod sursa (job #1883419)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX = 2000005;
int lps[MAX];
int main()
{
string s1,s2;
int len,i,j,len2;
vector<int> ans;
fstream f("strmatch.in",ios::in);
ofstream g("strmatch.out");
f>>s1>>s2;
len = s1.length();
len2 = s2.length();
lps[0] = 0;
j=0;
for(i=1;i<len;++i)
{
while(j>0 && s1[i-1]!=s1[j])
{
j = lps[j];
}
if(s1[i-1] == s1[j])
{
++j;
}
lps[i] = j;
}
i = j = 0;
while(i<len2)
{
while(s1[j]==s2[i])
{
++j;
++i;
}
if(j==len)
{
ans.push_back(i-len);
j = lps[j-1];
}
else if(i <len2 && s1[j]!=s2[i])
{
if(j!=0)
{
j=lps[j-1];
}
else
++i;
}
}
len = ans.size();
g<<len<<"\n";
for(i=0;i<len && i<1000;++i)
{
g<<ans[i]<<" ";
}
return 0;
}