Pagini recente » Cod sursa (job #1079810) | Cod sursa (job #249963) | Cod sursa (job #238971) | Cod sursa (job #1719358) | Cod sursa (job #840445)
Cod sursa(job #840445)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, s;
int l, r, z[4000004], nr, n, sol[2000001];
int main()
{
fin >> a >> b;
s = a+'$'+b;
n = s.size();
for ( int i = 1; i < n; i++ )
{
if ( i > r )
{
l = r = i;
while ( r < n && s[r-l] == s[r] )
r++;
z[i] = r-l;
r--;
}
else
{
int k = i-l;
if ( z[k] < r-i+1 )
z[i] = z[k];
else
{
l = i;
while ( r < n && s[r-l] == s[r] )
r++;
z[i] = r-l;
r--;
}
}
if ( z[i] == a.size() )
sol[++nr] = i - z[i] - 1;
}
fout << nr << '\n';
for ( int i = 1; i <= nr; i++ )
fout << sol[i] << ' ';
fin.close();
fout.close();
return 0;
}