Pagini recente » Cod sursa (job #848404) | Cod sursa (job #925028) | Cod sursa (job #243799) | Cod sursa (job #24215) | Cod sursa (job #2969587)
#include <bits/stdc++.h>
#define N 2000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nx,nstr;
queue<int> poz;
string x,str;
vector<int> trimitere(N,-1);
void Generare()
{
trimitere[0]=-1;
for(int i=1;i<nx;i++)
{
int aux=i-1;
if( x[ trimitere[aux]+1 ] == x[ i ] )trimitere[i]=trimitere[aux]+1;
else
{
aux=trimitere[aux];
while( trimitere[aux]!=-1 and aux>=0 )
{
if( x[ trimitere[aux]+1 ] == x[ i ] )
{
trimitere[i]=trimitere[aux]+1;
break;
}
aux=trimitere[aux];
}
}
}
}
void Rezolvare()
{
int aux=0;
for(int i=0;i<nstr;i++)
{
if( x[ aux ] == str[ i ] )
{
aux++;
if( aux==nx )
{
aux--;
aux=trimitere[aux]+1;
poz.push(i-nx+1);
}
}
else
{
while( trimitere[aux]!=-1 and aux>=0 )
{
if( x[ trimitere[aux]+1 ] == x[ i ] )
{
break;
}
aux=trimitere[aux];
}
}
}
fout << poz.size() << "\n";
while(!poz.empty())
{
fout << poz.front() << " ";
poz.pop();
}
}
int main()
{
fin >> x >> str;
fin.close();
nx= x.size();
nstr= str.size();
Generare();
Rezolvare();
fout.close();
return 0;
}