Pagini recente » Cod sursa (job #2615521) | Cod sursa (job #413069) | Cod sursa (job #3257835) | Cod sursa (job #2533331) | Cod sursa (job #2482367)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void build_lps(string &s,vector <int> &lps)
{
lps.push_back(0);
int i=0,j=1,n=s.size();
while(j<n)
{
if(s[i]==s[j])
++i,lps.push_back(i),++j;
else
{
if(i!=0)
i=lps[i-1];
else
{
lps.push_back(0);
++j;
}
}
}
}
int main()
{
string a,b;
getline(f,a);
getline(f,b);
vector <int> lps;
build_lps(a,lps);
int i=0,j=0,n=b.size(),m=a.size(),nr=0,k;
queue <int> q;
while(i<n)
{
if(b[i]==a[j])
++i,++j;
if(j==m)
q.push(i-j),++nr;
if(i<n && b[i]!=a[j])
if(j)
j=lps[j-1];
else
++i;
}
g<<nr<<'\n';
k=1;
while(!q.empty() && k<=1000)
{
g<<q.front()<<' ';
q.pop();
++k;
}
return 0;
}