Pagini recente » Cod sursa (job #1072687) | Cod sursa (job #147573) | Cod sursa (job #122649) | Cod sursa (job #1538044) | Cod sursa (job #1883364)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX = 2000001;
int lps[MAX];
int main()
{
string s1,s2;
int len,i,n,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;
i = 1;
while(i!=len)
{
if(s1[i] == s1[j])
{
++j;
lps[i]=j;
++i;
}
else
{
if(j!=0)
{
j = lps[j-1];
}
else
{
lps[i] = 0;
++i;
}
}
}
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)
{
if(j!=0)
{
j=lps[j-1];
}
else
++i;
}
}
len = ans.size();
g<<len<<"\n";
j=0;
for(i=0;i<len && j<1000;++i,++j)
{
g<<ans[i]<<" ";
}
return 0;
}