Pagini recente » Istoria paginii runda/test_mustang/clasament | Cod sursa (job #2068694) | Cod sursa (job #1351251) | Cod sursa (job #130163) | Cod sursa (job #1453467)
#include<fstream>
#include<cstring>
using namespace std;
ofstream fout("strmatch.out");
ifstream fin("strmatch.in");
const long int MMAX = 2000002;
int t, p, nr;
int table[MMAX], sol[MMAX];
char text[MMAX], pattern[MMAX];
void citire()
{
fin >> (pattern+1) >> (text+1);
t = strlen(text+1);
p = strlen(pattern+1);
}
void buildTable()
{
int x = 0;
for(int k=2; k<=p; k++) {
while(x && pattern[x+1] != pattern[k])
x = table[x];
if(pattern[x+1] == pattern[k])
x++;
table[k] = x;
}
}
void match()
{
for(int i=1, k=0; i<=t; i++) {
while(k && pattern[k+1] != text[i])
k = table[k];
if(pattern[k+1] == text[i])
k++;
if(k == p) {
if(nr <= 1000)
sol[++nr] = i-k;
else nr++;
k = table[k];
}
}
}
void afis()
{
fout << nr << '\n';
for(int i=1; i<=nr && i<=1000; i++)
fout << sol[i] << ' ';
fin.close();
fout.close();
}
int main()
{
citire();
buildTable();
match();
afis();
return 0;
}