Pagini recente » Cod sursa (job #962968) | Cod sursa (job #634281) | Cod sursa (job #633437) | Cod sursa (job #436492) | Cod sursa (job #3347368)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s1, s2;
int lps[2000005];
void build_lps()
{
int i = 1;
int len = 0;
while(i < s1.size())
{
if(s1[i] == s1[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len == 0)
{
i++;
}
else
{
len = lps[len - 1];
}
}
}
}
int main()
{
in>>s1>>s2;
build_lps();
vector<int> ans;
int i = 0;
int j = 0;
while(i < s2.size())
{
if(s1[j] == s2[i])
{
i++;
j++;
if(j == s1.size())
{
ans.push_back(i - s1.size());
j = lps[j - 1];
}
}
else
{
if(j == 0)
{
i++;
}
else
{
j = lps[j - 1];
}
}
}
out<<ans.size()<<'\n';
for(int i = 0; i<min((int)ans.size(), 1000); i++)
{
out<<ans[i]<<" ";
}
return 0;
}