Pagini recente » Cod sursa (job #1417825) | Cod sursa (job #2775667) | Cod sursa (job #604442) | Cod sursa (job #2444937) | Cod sursa (job #3193843)
#include <bits/stdc++.h>
#define N 2000008
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n;
char text[N], pattern[N];
int v[N];
void Citire()
{
fin >> pattern;
fin >> text;
n = strlen(pattern);
}
void Precalculare()
{
int i, j;
j = 0, i = 1;
while( i <= n )
{
if( pattern[j] == pattern[i] )
{
v[i] = j + 1;
i++;
j++;
}
else{
if( j == 0 ) {v[i] = 0; i++; continue;}
j = v[j - 1];
}
}
}
int k, sol[N];
void Rezolvare()
{
int i, j;
i = j = 0;
while( text[i] )
{
if( text[i] == pattern[j] ) j++, i++;
else{
if( j == 0 ) {i++; continue;}
j = v[j - 1];
}
if( j == n )
sol[++k] = i - n;
}
fout << k << "\n";
for( i=1; i<=min(k, 1000); i++ )
fout << sol[i] << " ";
}
int main()
{
Citire();
Precalculare();
Rezolvare();
return 0;
}