Pagini recente » Cod sursa (job #3334186) | Cod sursa (job #1406867) | Cod sursa (job #1521560) | Cod sursa (job #416357) | Cod sursa (job #1883443)
#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[1] = 0;
j=0;
for(i=2;i<=len;++i)
{
while(j>0 && s1[i-1]!=s1[j])
{
j = lps[j];
}
if(s1[i-1] == s1[j])
{
++j;
}
lps[i] = j;
}
j = 0;
for(i=1;i<=len2;++i)
{
while(j>0 && s1[j]!=s2[i-1])
{
j = lps[j];
}
if(s1[j]==s2[i-1])
++j;
if(j==len)
{
ans.push_back(i-j);
}
}
len = ans.size();
g<<len<<"\n";
for(i=0;i<len && i<1000;++i)
{
g<<ans[i]<<" ";
}
return 0;
}