Pagini recente » Cod sursa (job #1155892) | Cod sursa (job #1296928) | Cod sursa (job #1981445) | Cod sursa (job #2132789) | Cod sursa (job #1806135)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> getMatch(string s,string t)
{
int n=s.size();
int m=t.size();
//calcularea vectorului pi
vector <int> pi(n); //pi[i] = x litera cu indicele de pozitie i indica lungimea celui mai lung sufix care este si prefix
int k=-1;
pi[0]=-1; //initializam primul sufix care este si prefix ca avand lungime 0
for(int i=1;i<n;++i) //parcuregem toate caracterele sirului s
{
while(k!=-1 && s[k+1]!=s[i])
k=pi[k];
if(s[k+1]==s[i])
++k;
pi[i]=k;
}
//cautarea sirului t in sirul s
k=-1;
vector <int> v;
for(int i=0;i<m;++i)
{
while(k!=-1 && s[k+1]!=t[i])
k=pi[k];
if(s[k+1]==t[i])
++k;
if(k==n-1)
v.push_back(i-k);
}
return v;
}
int main()
{
string s,t;
getline(fin,s);
getline(fin,t);
vector <int> matches=getMatch(s,t);
fout<<matches.size()<<'\n';
for(int i=0;i<min(1000,int(matches.size()));++i)
fout<<matches[i]<<" ";
fin.close();
fout.close();
return 0;
}