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