Pagini recente » Cod sursa (job #1714545) | Cod sursa (job #1306036) | Cod sursa (job #693952) | Cod sursa (job #2465964) | Cod sursa (job #1724596)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");ofstream fout("strmatch.out");
string text,pattern;
vector <int> where;
int aparitii = 0;
vector <int> make_temp( string s )
{
vector <int> temp(s.size());
int j=0;
for(int i=1 ; i<s.size() ;)
{
if(s[i]==s[j]){temp[i]=j+1;i++;j++;}
else
{
if( j!=0 ) j=temp[j-1];
else{temp[i]=0;i++;}
}
}
return temp;
}
int main()
{
fin.sync_with_stdio(false);
fout.sync_with_stdio(false);
where.reserve(1000);
fin>>pattern>>text;
auto temp = make_temp( pattern );
if(pattern.size() > text.size()) fout<<0;
else
{
int i=0,j=0;
while( i<text.size() )
{
if(text[i]==pattern[j]){i++;j++;}
else
{
if( j != 0)
j=temp[j-1];
else
i++;
}
if( j == pattern.size() )
{
aparitii++;
i--;
if(aparitii<=1000)where.push_back(i-pattern.size()+1);
j=temp[j];
}
}
}
fout<<aparitii<<'\n';
for(auto i:where) fout<<i<< ' ';
return 0;
}