Pagini recente » Cod sursa (job #802301) | Cod sursa (job #580316) | Cod sursa (job #902683) | Cod sursa (job #2418160) | Cod sursa (job #2369297)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
string word, text;
fin>>word>>text;
vector <int> LPS(word.length(), 0);
vector <int> ans;
for(unsigned i = 1,j = 0; i < word.length();)
{
if(word[i] == word[j])
{
j++;
LPS[i] = j;
i++;
}
else
{
if(j != 0)
{
j = LPS[j - 1];
}
else
{
LPS[i] = 0;
i++;
}
}
}
for(unsigned i = 0, j = 0; i < text.length();)
{
if(word[j] == text[i])
{
i++;
j++;
}
if(j == word.length())
{
ans.push_back(i - word.length());
j = LPS[j - 1];
}
if(i < text.length() && word[j] != text[i])
{
if(j != 0)
{
j = LPS[j - 1];
}
else
{
i++;
}
}
}
fout<<ans.size()<<'\n';
if(ans.size() > 1000)
for(unsigned i = 0; i < 1000; i++)
fout<<ans[i]<<' ';
else
for(unsigned i = 0; i < ans.size(); i++)
fout<<ans[i]<<' ';
return 0;
}